binary - 在第一个 '1' 之前设置所有位

Question

假设一个 32 位无符号整数(可推广到任何大小的答案当然更好)。

这个整数可以假定为 2 的幂，所以只设置了一位。 我想设置整数中的所有位，除了那些低于设置位的位。因此(为简洁起见，使用 8 位整数)00001000 将变为 11111000。

这当然可以通过找到一个设置位然后遍历更高的位来完成，也可以设置它们。假设 highest_set 返回最高设置位的位置:

uint32_t f(uint32_t x)
{
  int n = highest_set(x);
  for (int i = 31; i != n; --i) {
      x |= 1 << i;
  }
  return x;
}

f 的运行时间确实取决于 x 的值，我觉得有一种更聪明的方法可以做到这一点。

Answer 1

从概念上讲，一件简单的事情就是取 x-1，然后将它与 0xffffffff 进行异或运算。将它写成 ~(x-1) 就像 harold 在下面的评论中所做的那样将处理不同大小的整数，而不必改变你正在与之进行异或运算的内容。