了解如何在C中使用按位运算符为数字计算尾随零 [英] UNDERSTANDING how to count trailing zeros for a number using bitwise operators in C

问题描述

注意-这不是此问题的重复-

Note - This is NOT a duplicate of this question - Count the consecutive zero bits (trailing) on the right in parallel: an explanation? . The linked question has a different context, it only asks the purpose of signed() being use. DO NOT mark this question as duplicate.

我一直在寻找一种方法来获取数字中的尾随零.我发现有点摇摆斯坦福大学在这里写上，它给出了以下内容解释.

I've been finding a way to acquire the number of trailing zeros in a number. I found a bit twiddling Stanford University Write up HERE here that gives the following explanation.

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;

为什么这最终会起作用?我对十六进制数字如何表示为二进制和按位运算符有所了解，但是我无法弄清楚此工作背后的直觉?什么是工作机制?

Why does this end up working ? I have an understanding of how Hex numbers are represented as binary and bitwise operators, but I am unable to figure out the intuition behind this working ? What is the working mechanism ?

推荐答案

代码已损坏(存在未定义的行为).这是一个固定的版本，它也较容易理解(可能更快):

The code is broken (undefined behavior is present). Here is a fixed version which is also slightly easier to understand (and probably faster):

uint32_t v;  // 32-bit word input to count zero bits on right
unsigned c;  // c will be the number of zero bits on the right
if (v) {
    v &= -v; // keep rightmost set bit (the one that determines the answer) clear all others
    c = 0;
    if (v & 0xAAAAAAAAu) c |= 1; // binary 10..1010
    if (v & 0xCCCCCCCCu) c |= 2; // binary 1100..11001100
    if (v & 0xF0F0F0F0u) c |= 4;
    if (v & 0xFF00FF00u) c |= 8;
    if (v & 0xFFFF0000u) c |= 16;
}
else c = 32;

一旦知道只设置一位，就一次确定结果的一位，方法是同时测试结果为奇数的所有位，然后测试结果为2的所有位，以此类推.

Once we know only one bit is set, we determine one bit of the result at a time, by simultaneously testing all bits where the result is odd, then all bits where the result has the 2's-place set, etc.

原始代码是相反的，从结果集的所有位(在if (c) c--;之后)开始，然后确定哪个需要为零并清除它们.

The original code worked in reverse, starting with all bits of the result set (after the if (c) c--;) and then determining which needed to be zero and clearing them.

由于我们一次要学习一小部分输出，因此我认为使用位运算而非算术来构建输出更加清楚.

Since we are learning one bit of the output at a time, I think it's more clear to build the output using bit operations not arithmetic.

这篇关于了解如何在C中使用按位运算符为数字计算尾随零的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！