设置第一个“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)可以处理不同大小的整数，而不必更改您要进行异或运算的内容。