当前位置：文江博客话题详情

binary c bit-manipulation

查找二进制数中的尾随 0

发布于 2024-12-10 18:21:51 字数 378 浏览 0 评论 0 原文

如何查找二进制数中尾随零的数量？

我采用了 K&R 位计数示例来查找二进制数中的个数，并且我修改它以查找尾随零的尾随数量：

int bitcount(unsigned x)
{
  int b;
  for(b=0;x!=0;x>>=1)
  {
    if(x&01)
      break;
    else
      b++;
  }
}

我希望审查此方法。

原文

How to find number of trailing zeros in a binary number?

I took the K&R bitcount example for finding the number of ones in a binary number and I modified it to find the trailing number of trailing zeros:

int bitcount(unsigned x)
{
  int b;
  for(b=0;x!=0;x>>=1)
  {
    if(x&01)
      break;
    else
      b++;
  }
}

I would like to have this method reviewed.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

如梦亦如幻 2024-12-17 18:21:51

来自 https://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightParallel ，这是一种并行计算计数以提高效率的方法：

unsigned int v;      // 32-bit word input to count zero bits on right
unsigned int c = 32; // c will be the number of zero bits on the right
v &= -signed(v);
if (v) c--;
if (v & 0x0000FFFF) c -= 16;
if (v & 0x00FF00FF) c -= 8;
if (v & 0x0F0F0F0F) c -= 4;
if (v & 0x33333333) c -= 2;
if (v & 0x55555555) c -= 1;

From https://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightParallel, here's a way to compute the count in parallel for better efficiency:

unsigned int v;      // 32-bit word input to count zero bits on right
unsigned int c = 32; // c will be the number of zero bits on the right
v &= -signed(v);
if (v) c--;
if (v & 0x0000FFFF) c -= 16;
if (v & 0x00FF00FF) c -= 8;
if (v & 0x0F0F0F0F) c -= 4;
if (v & 0x33333333) c -= 2;
if (v & 0x55555555) c -= 1;

回复收藏 0 原文

酷炫老祖宗 2024-12-17 18:21:51

在 X86 平台上的 GCC 上，您可以使用 __builtin_ctz(no)
在 Microsoft X86 编译器上，您可以使用 _BitScanForward

它们都会发出 bsf 指令

回复收藏 0 原文

风吹雪碎 2024-12-17 18:21:51

另一种方法（令我惊讶的是这里没有提到）是构建一个包含 256 个整数的表，其中数组中的每个元素都是该索引的最低 1 位。然后，对于整数中的每个字节，您在表中查找。

像这样的东西（我没有花任何时间来调整它，这只是为了粗略地说明这个想法）：

int bitcount(unsigned x)
{
   static const unsigned char table[256] = { /* TODO: populate with constants */ };

   for (int i=0; i<sizeof(x); ++i, x >>= 8)
   {
      unsigned char r = table[x & 0xff];

      if (r)
         return r + i*8;    // Found a 1...
   }

   // All zeroes...
   return sizeof(x)*8;
}

对于像这样的问题，一些表驱动方法的想法是 if语句在分支预测方面会花费一些成本，因此您应该致力于减少它们。它还减少了位移的数量。您的方法执行 if 语句和每位移位，而此方法对每个字节执行一次移位。（希望优化器可以展开 for 循环，而不是为此发出比较/跳转。）其他一些答案的 if 语句比这更少，但表方法很简单且易于执行理解。当然，您应该以实际测量为指导，看看这些是否重要。

Another approach (I'm surprised it's not mentioned here) would be to build a table of 256 integers, where each element in the array is the lowest 1 bit for that index. Then, for each byte in the integer, you look up in the table.

Something like this (I haven't taken any time to tweak this, this is just to roughly illustrate the idea):

int bitcount(unsigned x)
{
   static const unsigned char table[256] = { /* TODO: populate with constants */ };

   for (int i=0; i<sizeof(x); ++i, x >>= 8)
   {
      unsigned char r = table[x & 0xff];

      if (r)
         return r + i*8;    // Found a 1...
   }

   // All zeroes...
   return sizeof(x)*8;
}

The idea with some of the table-driven approaches to a problem like this is that if statements cost you something in terms of branch prediction, so you should aim to reduce them. It also reduces the number of bit shifts. Your approach does an if statement and a shift per bit, and this one does one per byte. (Hopefully the optimizer can unroll the for loop, and not issue a compare/jump for that.) Some of the other answers have even fewer if statements than this, but a table approach is simple and easy to understand. Of course you should be guided by actual measurements to see if any of this matters.

回复收藏 0 原文

书间行客 2024-12-17 18:21:51

int countTrailZero(unsigned x) {
    if (x == 0) return DEFAULT_VALUE_YOU_NEED;
    return log2 (x & -x);  
}

解释：

x & -x 返回设置为 1 的最右边位的数量

。例如 6 -> “0000,0110”，(6&-6)→ "0000,0010"

您可以将其减去两个补数：
x = "a1b"，其中 b 代表所有尾随零。
那么

-x = !(x) + 1 = !(a1b) + 1 = (!a)0(!b) + 1 = (!a)0(1...1) + 1 = (!a)1(0...0) = (!a)1b

;

x & (-x) = (a1b) & (!a)1b = (0...0)1(0...0)

您只需执行 log2 即可获取尾随零的数量。

int countTrailZero(unsigned x) {
    if (x == 0) return DEFAULT_VALUE_YOU_NEED;
    return log2 (x & -x);  
}

Explanation:

x & -x returns the number of right most bit set with 1.

e.g. 6 -> "0000,0110", (6 & -6) -> "0000,0010"

You can deduct this by two complement:
x = "a1b", where b represents all trailing zeros.
then

-x = !(x) + 1 = !(a1b) + 1 = (!a)0(!b) + 1 = (!a)0(1...1) + 1 = (!a)1(0...0) = (!a)1b

x & (-x) = (a1b) & (!a)1b = (0...0)1(0...0)

you can get the number of trailing zeros just by doing log2.

回复收藏 0 原文

给妤﹃绝世温柔 2024-12-17 18:21:51

我认为你的方法是有效的（尽管你可能想使用unsigned int）。每次都检查最后一位数字，如果它为零，则将其丢弃，并增加尾随零位的数量。

我认为对于尾随零，您不需要循环。

考虑以下问题：

如果减去 1，数字（当然是二进制表示形式）会发生什么？哪些数字发生变化，哪些保持不变？
如何将原始数字和递减版本组合起来，以便只留下表示尾随零的位？

如果正确应用上述步骤，您只需在 O(lg n) 步骤中找到设置的最高位（查看）。

回复收藏 0 原文

影子是时光的心 2024-12-17 18:21:51

应该是：

int bitcount(unsigned char x)
{
  int b;
  for(b=0; b<7; x>>=1)
  {
    if(x&1)
      break;
    else
      b++;
  }
  return b;
}

或者甚至

int bitcount(unsigned char x)
{
  int b;
  for(b=0; b<7 && !(x&1); x>>=1) b++;
  return b;
}

或者甚至（耶！）

int bitcount(unsigned char x)
{
  int b;
  for(b=0; b<7 && !(x&1); b++) x>>=1;
  return b;
}

或者...

啊，无论如何，那里有 1005 亿种方法可以做到这一点。使用您需要或喜欢的任何东西。

Should be:

int bitcount(unsigned char x)
{
  int b;
  for(b=0; b<7; x>>=1)
  {
    if(x&1)
      break;
    else
      b++;
  }
  return b;
}

or even

int bitcount(unsigned char x)
{
  int b;
  for(b=0; b<7 && !(x&1); x>>=1) b++;
  return b;
}

or even (yay!)

int bitcount(unsigned char x)
{
  int b;
  for(b=0; b<7 && !(x&1); b++) x>>=1;
  return b;
}

or ...

Ah, whatever, there are 100500 millions methods of doing this. Use whatever you need or like.

回复收藏 0 原文

花落人断肠 2024-12-17 18:21:51

我们可以使用位运算轻松获得它，我们不需要遍历所有位。伪代码：

int bitcount(unsigned x) {
    int xor = x ^ (x-1); // this will have (1 + #trailing 0s) trailing 1s
    return log(i & xor); // i & xor will have only one bit 1 and its log should give the exact number of zeroes
}

We can easily get it using bit operations, we don't need to go through all the bits. Pseudo code:

int bitcount(unsigned x) {
    int xor = x ^ (x-1); // this will have (1 + #trailing 0s) trailing 1s
    return log(i & xor); // i & xor will have only one bit 1 and its log should give the exact number of zeroes
}

回复收藏 0 原文

岛徒 2024-12-17 18:21:51

使用现已发布的 C23，代码可以考虑：

//Returns the number of consecutive 1 bits in value, starting from the most significant bit.
// C23dr 7.18.5
stdc_trailing_zeros_**()

#include <stdbit.h>
unsigned int stdc_trailing_zeros_uc(unsigned char value);
unsigned int stdc_trailing_zeros_us(unsigned short value);
unsigned int stdc_trailing_zeros_ui(unsigned int value);
unsigned int stdc_trailing_zeros_ul(unsigned long value);
unsigned int stdc_trailing_zeros_ull(unsigned long long value);
generic_return_type stdc_trailing_zeros(generic_value_type value);

With C23, now released, code can consider:

//Returns the number of consecutive 1 bits in value, starting from the most significant bit.
// C23dr 7.18.5
stdc_trailing_zeros_**()

#include <stdbit.h>
unsigned int stdc_trailing_zeros_uc(unsigned char value);
unsigned int stdc_trailing_zeros_us(unsigned short value);
unsigned int stdc_trailing_zeros_ui(unsigned int value);
unsigned int stdc_trailing_zeros_ul(unsigned long value);
unsigned int stdc_trailing_zeros_ull(unsigned long long value);
generic_return_type stdc_trailing_zeros(generic_value_type value);

回复收藏 0 原文

~没有更多了~