问题描述
我有一个类型为Long Long的整数,在删除该整数的二进制表示形式中存在的尾随零后,我要将其转换为新的整数。
推荐答案
以下是一种暴力方法:
long long remove_trailing_zeroes(long long v) {
if (v != 0) {
while ((v & 1) == 0)
v /= 2;
}
return v;
}
以下是无符号数的直接方法,但除法可能比上面的迭代更昂贵:
unsigned long long remove_trailing_zeroes(unsigned long long v) {
if (v != 0) {
// v and (v - 1) differ only in the trailing 0 bits plus 1
// shifting v ^ (v - 1) right by 1 and adding 1 gives the power of 2
// by which to divide v to remove all trailing 0 bits
v /= (((v ^ (v - 1)) >> 1) + 1);
}
return v;
}
Harold建议简化:
unsigned long long remove_trailing_zeroes(unsigned long long v) {
if (v != 0) {
// `-v`, which is `(~v + 1)` has all bits flipped except the least
// significant 1 bit.
// dividing v by `-v & v` shifts all trailing zero bits out,
v /= -v & v;
}
return v;
}
可以简化为单个表达式:
unsigned long long remove_trailing_zeroes(unsigned long long v) {
return v ? v / (-v & v) : v;
}
为了避免除法,您可以用一种有效的方法计算v ^ (v - 1)
中的位数,并将v
右移比这个数字小一。这也适用于0
,因此您将获得无分支代码。
你可以在Bit Twiddling Hacks
这个迷人的词中找到其他方法