检查int的位以查看它们是否共享2的幂的二进制数(仅按位) [英] Checking bits of ints to see if they share binary with the power of 2 (bitwise only)

问题描述

我正在尝试重新创建此功能:

I'm trying to recreate this function:

int test(int x) {
   int i;
   for (i = 0; i < 32; i+=2)
   if ((x & (1<<i)) == 0)
      return 0;
   return 1; 
}

但仅使用以下按位运算符:！，〜，&，^，|，+，<<和>> (这意味着没有循环或if语句)

But only using these bit-wise operators: !, ~, &, ^, |, +, <<, and >> (Meaning no loops or if statements either)

我对这个问题非常困惑，我一直盯着它看了一个小时，但仍然不确定从哪里开始.

I am so confused with this question I have been staring at it for like a hour and am still not sure where to start.

我了解基本上是x将它与2 ^ i(其中i为0-31)进行比较，然后如果x和2 ^ i不共享任何相同的位，则返回0，否则返回1.

I understand that basically it is taking x comparing it with 2^i where i is 0-31 and then returning 0 if x and 2^i do not share any of the same bits and returning 1 otherwise.

但是我觉得有一个更简单，不拘泥于焦点的解释可以更好地总结这一点，并且如果有人甚至可以给我这将是巨大的帮助.

But I feel like there is a more simple, non-bit focused explanation that summarizes this better and if someone could even just give me that it would be a huge help.

推荐答案

如上所述，最小的解决方案是

As has already been stated, the minimal solution would be

return (x & 0x55555555) == 0x55555555 ;

但是，它使用'=='，它不在允许的运算符列表中.整数比较或多或少地等同于看数字之间的差是否为零，但-"也不在允许的运算符列表中，而"+"则在列表中.将有符号整数的第一位设置为等于使其为负并减去1.因此，该函数可以写为:

However, this uses '==', which is not in the list of allowed operators. Comparisons of integers is more or less equivalent to seeing if the difference between the numbers is zero or not, but '-' is also not in the list of allowed operators, but '+' is. Setting the first bit in a signed integer is equivalent to making it negative and subtracting 1. Therefore, the function can be written as:

return !(((x & 0x55555555) | 0x80000000) + 0x55555556);

这假设输入不是负数，并且对于很大的输入它似乎也失败了，但是在我的测试中适用于0到1431655764范围内的数字. 此外，该操作还假设使用32位整数.

This assumes the input is not negative, and it also seems to fail for very large input, but works for numbers in the range 0 to 1431655764 in my tests. Also, this assumes 32-bit integers.

XOR运算符显然可以更好地替代'==':

The XOR operator is obviously a much better substitute for '==':

return !((x & 0x55555555) ^ 0x55555555);

也可以使用负数！

这篇关于检查int的位以查看它们是否共享2的幂的二进制数(仅按位)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！