如何翻转一个数的所有位(除了最高位及之后的位)?
例如:假设有一个需要翻转的32位数字。
00000000000000000010011110000100 // Input
00000000000000000001100001111011 // Expected
我怎样才能在Java/C++中实现这个?
如何翻转一个数的所有位(除了最高位及之后的位)?
例如:假设有一个需要翻转的32位数字。
00000000000000000010011110000100 // Input
00000000000000000001100001111011 // Expected
我怎样才能在Java/C++中实现这个?
n = 10011110000100
为例:
v = 100...00
,使得 v > n
。result = n ^ (v - 1)
(注意,b XOR 1
可以 切换 第 b
位的值)。n = 10011110000100
v = 100000000000000
v - 1 = 11111111111111
n ^ (v - 1) = 01100001111011
代码:
int n = 0b10011110000100;
int v = 1;
while (v <= n)
v <<= 1;
int result = n ^ (v - 1);
你可以像这样做:
public static int toggle(int n) {
int m = n;
m |= m >>> 1;
m |= m >>> 2;
m |= m >>> 4;
m |= m >>> 8;
m |= m >>> 16;
return n ^ m;
}
重复的以2的幂次方为主的行,其目的是将n
的最高位比特和所有比它低的比特设置为m
,可以通过使用特殊指令来查找前导零的数量来替换。
如果您可以访问这种功能,那么可以用这种方式替换代码。
def toggle(n)
shift = 1
m = n
while (1 << shift) <= n
m |= m >> shift
shift <<= 1
end
m ^ n
end
def toggle(n):
shift = 1
m = n
while (1 << shift) <= n:
m |= m >> shift
shift <<= 1
return m ^ n
您使用了标签language-agnostic
,因此我会按照您的意思进行翻译,即使您在问题中提到了C++和Java。