并行计算右边的连续零位（跟踪）：解释？ [英] Count the consecutive zero bits (trailing) on the right in parallel: an explanation?

问题描述

请考虑来自Bit Twiddling Hacks网站的此链接。
为了计算尾随位，使用以下算法：

Consider this link from the Bit Twiddling Hacks website. In order to count the trailing bits, the following algorithm is used:

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); /* THIS LINE */
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;

有人可以向我解释标为 / *的那行的作用吗？ * / ，更重要的是，可以仅使用按位运算来避免使用 signed（）吗？

Can someone explain me the role of the line marked as /* THIS LINE */ and more importantly is it possible to use only bitwise operations to avoid the use of signed() ?

编辑：如何用算术/逻辑/按位运算替换 signed（）？

How to replace signed() by arithmetic/logical/bitwise operations?

推荐答案

v& = -signed（v）将清除除最低设置位（ 1 < v的/ code>位），即从v提取最低有效1位（之后v将变为2的幂）。例如，对于 v = 14（1110），此后，我们有 v = 2（0010）。

v &= -signed(v) will clear all but the lowest set bit (1-bit) of v, i.e. extracts the least significant 1 bit from v (v will become a number with power of 2 afterwards). For example, for v=14 (1110), after this, we have v=2 (0010).

此处，使用 signed（）是因为v是 unsigned ，而您正试图否定一个 unsigned 值（VS2012导致编译错误）（JoelRondeau的评论）。否则，您会收到这样的警告： 警告C4146：一元减运算符应用于无符号类型，结果仍为无符号 （我的测试）。

Here, using signed() is because v is unsigned and you're trying to negate an unsigned value (gives compilation error with VS2012) (comment from JoelRondeau). Or you will get a warning like this: warning C4146: unary minus operator applied to unsigned type, result still unsigned (my test).

这篇关于并行计算右边的连续零位（跟踪）：解释？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！