位运算符

Question

我正在使用一个函数，但遇到了一些麻烦。我们只能使用位运算符（这意味着不能使用逻辑运算符、循环或if语句），且不允许使用大于0xFF的常量。

我已经让函数正常工作了，但它使用了一个巨大的常量。当我尝试使用较小的数字和移位来实现它时，我无法让它正常工作，也不确定原因在哪里。

该函数应检查给定整数中的所有偶数位，并在它们都设置为1时返回1。

有效代码

 int allEvenBits(int x) {
 /* implements a check for all even-numbered bits in the word set to 1 */
 /* if yes, the program outputs 1 WORKING */

 int all_even_bits = 0x55555555;
 return (!((x & all_even_bits) ^ all_even_bits)); 
 }

尝试使用较小的常数和移位进行实现

int allEvenBits(int x) {
/* implements a check for all even-numbered bits in the word set to 1 */
/* if yes, the program outputs 1 WORKING */

int a, b, c, d, e = 0;
int mask = 0x55;

/* first 8 bits */
a = (x & mask)&1;

/* second eight bits */
b = ((x>>8) & mask)&1;

/* third eight bits */
c = ((x>>16) & mask)&1;

/* fourth eight bits */
d = ((x>>24) & mask)&1;
e = a & b & c & d;
return e;
}

我在这里做错了什么吗？

- rcbranham

---

你也可以从足够小的常量构建该掩码，然后使用你知道有效的代码。 - harold

Answer 1

我不知道你为什么要将你的值与1进行AND运算。这样做的目的是什么？

这段代码没有经过测试，但我会按照以下方式处理。

int allEvenBits(int x) {
    return (x & 0x55 == 0x55) &&
        ((x >> 8) & 0x55 == 0x55) &&
        ((x >> 16) & 0x55 == 0x55) &&
        ((x >> 24) & 0x55 == 0x55);
} 

- Jonathan Wood

---

no loops or if statements - Iłya Bursov

好的，我错过了那个要求。我更新了我的答案。 - Jonathan Wood

对于有符号整数的右移操作为未定义行为。 - abligh

@JonathanWood ISO/IEC 9899:TC3 6.5.7/5“E1 >> E2”的结果为将E1向右移动E2位。如果E1具有无符号类型或者E1具有有符号类型并且是非负值，则结果的值为E1 / 2E2的整数部分。如果E1具有有符号类型并且是负值，则结果的值为实现定义。 - abligh

@abligh：但我看不出来那会如何影响我发布的代码结果，因为它掩盖了我感兴趣的位。 - Jonathan Wood

Answer 2

当你执行以下操作时，比如这样：

d = ((x>>24) & mask)&1;

实际上，您正在检查最低位（值为1）是否设置，而不是任何掩码位是否设置...因为最后的&1对其余部分的结果进行按位与运算，与1。如果将&1更改为== mask，则当在（x>>24）中设置了mask中设置的所有位时，您将获得1，这是预期的。当然，其他类似行也存在同样的问题。

如果您不能使用 == 或！= 等比较，则需要将所有有趣的位移动到相同的位置，然后将它们一起AND，并使用掩码消除其他位位置。两步操作如下：

/* get bits that are set in every byte of x */
x = (x >> 24) & (x >> 16) & (x >> 8) & x;
/* 1 if all of bits 0, 2, 4 and 6 are set */
return (x >> 6) & (x >> 4) & (x >> 2) & x & 1;

- Dmitri

---

d = ((x>>24) & mask) && 1; 这是 if 的简写形式，根据要求测试所有偶数位是否为1，实际上是错误的。 - Iłya Bursov

@Lashane 这不是 if... 这是逻辑与，当条件为真时返回1，否则返回0。 - Dmitri

no logical operators - Iłya Bursov

同时，逻辑运算返回“非零”表示为真，可能是0xff或0x80。 - Iłya Bursov

@Lashane 逻辑与运算符实际上需要返回1表示为真。 - Dmitri

Answer 3

如果您不被允许使用大于 0xff 的常量，并且您现有的程序可以正常工作，那么考虑将以下内容替换：

int all_even_bits = 0x55555555;

由：

int all_even_bits = 0x55;
all_even_bits |= all_even_bits << 8;  /* it's now 0x5555 */
all_even_bits |= all_even_bits << 16; /* it's now 0x55555555 */

一些其他答案会对有符号整数（即int）进行右移，这是未定义的行为。

另一种选择是：

int allevenbitsone(unsigned int a)
{
    a &= a>>16; /* superimpose top 16 bits on bottom */ 
    a &= a>>8;  /* superimpose top 8 bits on bottom */
    a &= a>>4;  /* superimpose top 4 bits on bottom */
    a &= a>>2;  /* and down to last 2 bits */
    return a&1; /* return & of even bits */
}

这段代码的作用是将偶数位的16位与运算后放在第0位，奇数位的16位与运算后放在第1位，最后返回第0位。

- abligh

Answer 4

假设你正在检查前4个最低有效数字，其中偶数位会生成1010。现在，你需要将其与要检查的数字的前4位进行 AND 运算。所有1都应该保留在那里。因此，对于最低有效位的4位，测试应该是((number & mask) == mask)（mask为1010），你可以按照4位或8位的块来执行此操作（或者您可以使用8位，因为允许这样做）。

- mrk

Answer 5

你代码中的主要问题是你正在执行 &1 操作，因此你从数字中取出前8位，用0x55掩码处理它们，然后只使用第1位，这是错误的。

考虑直接的方法：

int evenBitsIn8BitNumber(int a) {
    return (a & (a>>2) & (a>>4) & (a>>6)) & 1;
}

int allEvenBits(int a) {
    return evenBitsIn8BitNumber(a) &
        evenBitsIn8BitNumber(a>>8) &
        evenBitsIn8BitNumber(a>>16) &
        evenBitsIn8BitNumber(a>>24);
}

- Iłya Bursov

---

对有符号整数进行右移操作是未定义的行为。 - abligh

@abligh 实际上这是_实现相关的_，无论如何 - 对于这段代码来说，符号位是否被提升都没有区别。 - Iłya Bursov