最高有效设置位左侧未设置位的数量？

Question

假设 64 位整数 0x000000000000FFFF 表示为

00000000 00000000  00000000 00000000
00000000 00000000 >11111111 11111111

如何找到最高有效设置位（标有 > 的位）左侧未设置位的数量？

Answer 1

在直接 C 中（在我的设置中，long long 是 64 位），取自类似的 Java 实现：（在阅读更多汉明权重后更新）

更多解释：顶部部分只是将所有位设置在最重要的右侧1，然后否定它。 （即最重要的 1 的“左边”的所有 0 现在都是 1，其他所有都是 0）。

然后我使用 汉明权重 实现来计算位数。

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);

我很想知道这是如何提高效率的。不过，用几个值对其进行了测试，它似乎有效。

Answer 2

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

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，这就正确地完成了计算。

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() 函数，如 这个问题。

Answer 4

// 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< /a> 用于各种位计数技术。

Answer 5

我不确定我是否正确理解了这个问题。我认为你有一个 64 位值并且想要找到其中前导零的数量。

一种方法是找到最高有效位并简单地从 63 中减去它的位置（假设最低位是位 0）。您可以通过测试是否在所有 64 位的循环内设置某个位来找出最高有效位。

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

Answer 6

我同意二分查找的想法。不过，这里有两点很重要：

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);
}

Answer 7

就这样，当您需要其他尺寸时，更新起来非常简单......

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;
}

Answer 8

与user470379的想法相同< /a>，但是倒计时...
假设所有 64 位均未设置。当值大于 0 时，继续将值右移并减少未设置位的数量：

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

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;
}

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)