标签: bit-manipulation

我遇到过一个(看似很奇怪的)非常奇怪的案子.

取数字2(0b10)并用1(0b01)进行位掩码

这应该产生0b00相当于0的东西.

然而,这里是薛定谔先生进来的地方:

var_dump(0b10 & 0b01); // int(0)
var_dump(0b10 & 0b01 == 0); // int(0)
var_dump(0b10 & 0b01 != 0); // int(0)

威士忌酒.探戈.狐步舞.

不可否认,对于按位运算符来说,我并不是最敏锐的 - 所以也许我在某个地方有可怕的,可怕的错误？

但是,在Python中:

0b10 & 0b01 == 0 = True

0b10 & 0b01 != 0 = False

...所以？

我需要一个这样的函数:

// return true iff 'n' is a power of 2, e.g.
// is_power_of_2(16) => true  is_power_of_2(3) => false
bool is_power_of_2(int n);

任何人都可以建议我怎么写这个？你能告诉我一个可以找到这种算法的好网站吗？

引用用于计算整数绝对值(abs)的代码而不分支来自http://graphics.stanford.edu/~seander/bithacks.html:

int v;           // we want to find the absolute value of v
unsigned int r;  // the result goes here 
int const mask = v >> sizeof(int) * CHAR_BIT - 1;

r = (v + mask) ^ mask;

专利变化:

r = (v ^ mask) - mask;

CHAR_BIT它是什么以及如何使用它？

左右移位运算符(<<和>>)已在C++中可用.但是,我无法找到如何执行循环移位或旋转操作.

如何执行"向左旋转"和"向右旋转"等操作？

在这里向右旋转两次

Initial --> 1000 0011 0100 0010

应该导致:

Final   --> 1010 0000 1101 0000

一个例子会有所帮助.

(编者注:如果旋转计数为零,许多常见的表达方式在C中旋转会受到未定义的行为的影响,或者编译为不止一个旋转机器指令.这个问题的答案应记录最佳实践.)

java.util.Random源代码294行说

if ((n & -n) == n) // i.e., n is a power of 2
    // rest of the code

为什么是这样？

我需要测试位值为 1 的位置（对于 32 位整数从 0 到 31）是否形成连续区域。例如：

00111111000000000000000000000000      is contiguous
00111111000000000000000011000000      is not contiguous

我希望这个测试，即一些功能has_contiguous_one_bits(int)，是可移植的。

一个明显的方法是遍历位置以找到第一个设置位，然后是第一个未设置位并检查是否有更多设置位。

我想知道是否存在更快的方法？如果有找到最高和最低设置位的快速方法（但从这个问题看来没有任何可移植的），那么可能的实现是

bool has_contiguous_one_bits(int val)
{
    auto h = highest_set_bit(val);
    auto l = lowest_set_bit(val);
    return val == (((1 << (h-l+1))-1)<<l);
}

只是为了好玩，这里是前 100 个具有连续位的整数：

0 1 2 3 4 6 7 8 12 14 15 16 24 28 30 31 32 48 56 60 62 63 64 96 112 120 124 126 127 128 192 224 240 248 252 254 …

如何仅使用位移和加法进行乘法和除法？

想象一下,我有两个无符号字节b和x.我需要计算bsubas b - x和baddas b + x.但是,我不希望在这些操作期间发生下溢/溢出.例如(伪代码):

b = 3; x = 5;
bsub = b - x; // bsub must be 0, not 254

和

b = 250; x = 10;
badd = b + x; // badd must be 255, not 4

显而易见的方法包括分支:

bsub = b - min(b, x);
badd = b + min(255 - b, x);

我只是想知道是否有更好的方法来做到这一点,即通过一些hacky位操作？

我读到结构中位字段的顺序是特定于平台的.如果我使用不同的特定于编译器的打包选项,这将保证数据在写入时以正确的顺序存储吗？例如:

struct Message
{
  unsigned int version : 3;
  unsigned int type : 1;
  unsigned int id : 5;
  unsigned int data : 6;
} __attribute__ ((__packed__));

在具有GCC编译器的英特尔处理器上,字段在显示时显示在内存中.Message.version是缓冲区中的前3位,然后Message.type是.如果我找到各种编译器的等效结构包装选项,这将是跨平台的吗？

您是否曾经在实际编程项目中使用位移？大多数(如果不是全部)高级语言都有移位运算符,但什么时候你真的需要使用它们？