最高位设置位左侧未设置位的数量是多少？

Question

假设64位整数0x000000000000FFFF，其表示为：

00000000 00000000  00000000 00000000
00000000 00000000 >11111111 11111111

我该如何找到最高位的设置位（用 > 标记）左侧未设置位的数量？

- thr

---

你对C、C#或C++感兴趣吗？理论是相同的，但语言不同。 - Binary Worrier

既然我假设有一些位操作的魔法来完成这个任务，并且在所有语言中看起来几乎相同，那么这并不重要。 - thr

谷歌搜索"fxtbook.pdf"，第1.6.1章。 - Hans Passant

如果这个值始终符合01（所有0后跟所有1）的模式，那么您可以采取许多快捷方式，是这种情况吗？ - jkerian

@jkerian 是的...那么它只是64 - bitcount(value)。搜索popcount或Debruijn以了解高效计算位的方法。 - Jim Balter

Answer 1

在我的设置中，使用纯C（long long为64位），取自类似的Java实现：（在更多关于汉明重量的阅读后更新）

稍微解释一下：顶部部分只是将最高有效位右侧的所有位设置为1，然后对其进行否定。（即，在最高有效1的“左侧”的所有0现在都是1，其他所有内容都是0）。

然后我使用了一个Hamming Weight实现来计算比特数。

unsigned long long i = 0x0000000000000000LLU;

i |= i >> 1;
i |= i >> 2;
i |= i >> 4;
i |= i >> 8;
i |= i >> 16;
i |= i >> 32;
// Highest bit in input and all lower bits are now set. Invert to set the bits to count.
i=~i;

i -= (i >> 1) & 0x5555555555555555LLU; // each 2 bits now contains a count
i = (i & 0x3333333333333333LLU) + ((i >> 2) & 0x3333333333333333LLU); // each 4 bits now contains a count
i = (i + (i >> 4)) & 0x0f0f0f0f0f0f0f0fLLU; // each 8 bits now contains a count 
i *= 0x0101010101010101LLU; // add each byte to all the bytes above it
i >>= 56; // the number of bits

printf("Leading 0's = %lld\n", i);

我很想看看这个在效率方面的表现如何。虽然我已经用几个值进行了测试，但它似乎可以正常工作。

- Dusty

Answer 2

基于：http://www.hackersdelight.org/HDcode/nlz.c.txt

template<typename T> int clz(T v) {int n=sizeof(T)*8;int c=n;while (n){n>>=1;if (v>>n) c-=n,v>>=n;}return c-v;}

如果您想要一份让您能够保持午餐不反胃的版本，这里是：

int clz(uint64_t v) {
    int n=64,c=64;
    while (n) {
        n>>=1;
        if (v>>n) c-=n,v>>=n;
    }
    return c-v;
}

如您所见，通过对汇编代码的仔细分析，您可以节省循环次数，但这里的策略并不是一个可怕的策略。while循环将运行Lg[64]=6次；每次它都会将问题转化为计算一个半大小整数的前导位数的问题。 while循环内部的if语句询问：“我能用一半的位数来表示这个整数吗？”，或者类似地说：“如果我把它减半，我会失去它吗？”。在if()语句完成后，我们的数字将总是在最低的n位中。 在最后阶段，v要么是0要么是1，这样就正确地完成了计算。

- Dave Gamble

Answer 3

如果你正在处理无符号整数，你可以这样做：

#include <math.h>
int numunset(uint64_t number)
{
    int nbits = sizeof(uint64_t)*8;
    if(number == 0)
        return nbits;
    int first_set = floor(log2(number));
    return nbits - first_set - 1;
}

我不知道它在性能上与已经提供的循环和计数方法相比如何，因为log2()可能会很昂贵。

编辑：

这可能会导致一些问题，因为log2()函数将转换为double并且可能出现一些数值问题。您可以使用适用于long double的log2l()函数。更好的解决方案是使用整数log2()函数，如this question中所述。

- Jason B

---

哦，是的 log2 真的很耗费资源！我甚至都忘记了这种可能性。我不知道处理器FPU中这样的函数是如何实现的，但通常计算任何非算术函数都需要计算一些级数和。我认为这种事情需要大量的CPU周期。 - valdo

Answer 4

和user470379的想法一样，但是倒计时...
假设所有64位都未设置。当值大于0时，继续向右移动该值并递减未设置位数：

/* untested */
int countunsetbits(uint64_t val) {
    int x = 64;
    while (val) { x--; val >>= 1; }
    return x;
}

- pmg

---

请不要这样做。这个while()循环将执行64次。你可以通过二进制分割问题，在6个循环迭代中完成。请查看我的答案，基于Hacker's Delight实现。 - Dave Gamble

Answer 5

我同意二分查找的想法。然而，这里有两个重要的点：

1. 你问题的有效答案范围是从0到64（包括）。换句话说 - 可能有65个不同的答案。我认为（几乎确定）所有发布“二分查找”解决方案的人都忽略了这一点，因此他们将得到错误的答案，无论是零还是带有MSB位的数字。
2. 如果速度很关键 - 你可能想避免使用循环。有一种优雅的方法可以使用模板来实现。

以下模板内容可以正确地找到任何无符号类型变量的MSB。

// helper
template <int bits, typename T>
bool IsBitReached(T x)
{
    const T cmp = T(1) << (bits ? (bits-1) : 0);
    return (x >= cmp);
}

template <int bits, typename T>
int FindMsbInternal(T x)
{
    if (!bits)
        return 0;

    int ret;
    if (IsBitReached<bits>(x))
    {
        ret = bits;
        x >>= bits;
    } else
        ret = 0;

    return ret + FindMsbInternal<bits/2, T>(x);
}

// Main routine
template <typename T>
int FindMsb(T x)
{
    const int bits = sizeof(T) * 8;
    if (IsBitReached<bits>(x))
        return bits;

    return FindMsbInternal<bits/2>(x);
}

- valdo

Answer 6

这里是代码，如果你需要适应其他尺寸，更新起来非常简单...

int bits_left(unsigned long long value)
{
  static unsigned long long mask = 0x8000000000000000;
  int c = 64;
  // doh
  if (value == 0)
    return c;

  // check byte by byte to see what has been set
  if (value & 0xFF00000000000000)
    c = 0;
  else if (value & 0x00FF000000000000)
    c = 8;
  else if (value & 0x0000FF0000000000)
    c = 16;
  else if (value & 0x000000FF00000000)
    c = 24;
  else if (value & 0x00000000FF000000)
    c = 32;
  else if (value & 0x0000000000FF0000)
    c = 40;
  else if (value & 0x000000000000FF00)
    c = 48;
  else if (value & 0x00000000000000FF)
    c = 56;

  // skip
  value <<= c;

  while(!(value & mask))
  {
    value <<= 1;
    c++;
  }

  return c;
}

- Nim

Answer 7

// clear all bits except the lowest set bit
x &= -x;     

// if x==0, add 0, otherwise add x - 1. 
// This sets all bits below the one set above to 1.
x+= (-(x==0))&(x - 1);

return 64 - count_bits_set(x);

count_bits_set 是你能找到的最快版本的计算位数的方法。请访问 https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel 了解各种位计数技术。

- MSN

---

就目前而言，第一行不是清除了除了“最低位”设置的所有位吗？ - Jeppe Stig Nielsen

@JeppeStigNielsen，啊，原来是这样！回想起来，我不确定为什么会这样回答。 - MSN

-1 这怎么可能被接受了？它完全是错的。首先，它试图计算比最低位设置的位数更高的位数，这不是所要求的。其次，第二行中的条件是反向的。前两行的期望效果可以通过 if (x) x ^= x-1 实现...但只要进行了测试，就可以做 if (!x) return ...，然后 0 可以映射到任何值。(最好是对于 0 让该函数未定义，并让调用者处理它。) - Jim Balter

Answer 8

我不确定我正确理解了问题。我认为您有一个64位值，并想找到其中前导零的数量。

一种方法是找到最高有效位，然后将其位置从63中简单地减去（假设最低位是位0）。您可以通过在所有64位上循环时测试是否设置了位来找出最高有效位。

另一种方法可能是使用gcc中的（非标准）__builtin_clz。

- MAK

Answer 9

尝试

int countBits(int value)
{
    int result = sizeof(value) * CHAR_BITS;  // should be 64

    while(value != 0)
    {
        --result;
        value = value >> 1; // Remove bottom bits until all 1 are gone.
    }
    return result;
}

- Martin York

Answer 10

使用以2为底的对数，可以得到最高位数字为1。

log(2) = 1, meaning 0b10 -> 1
log(4) = 2, 5-7 => 2.xx, or 0b100 -> 2
log(8) = 3, 9-15 => 3.xx, 0b1000 -> 3
log(16) = 4 you get the idea

等等……

在这些数字之间，它们变成了对数结果的分数。因此，将该值强制转换为int类型会给出最重要的数字。

一旦您得到这个数字，比如b，简单的64-n就是答案。

function get_pos_msd(int n){
    return int(log2(n))
}

last_zero = 64 - get_pos_msd(n)

- Perennial