C++中 x & -x 表示含义

发布时间:2022-09-13 22:31:24
贴主:52啥都不会
热度:5

52啥都不会 2022-09-13

来源:

当我在刷题,学习(借鉴)大佬的代码的时候,经常看到 “(x & -x) == x”

说明:

-x 的值,其实就是在x的值的基础上进行按位取反(~x)之后在增加1所得, 也就是说

x & -x == x & (~x + 1)。

1.x 为偶数我们都知道, 当一个奇数 + 1时, 表示的二进制数则会发生进位, 这样的话, 会产生一个连锁反应,也就是最低位的那些连续的1都会被清0,

0000 0000 0111 1111 + 1 = 0000 0000 1000 0000

如果一个偶数, 如 0000 0100 1110, 取反后的结果就变成了 1111 1011 0001,而当这个值 + 1之后由于发生了进位, 即
1111 1011 0001 + 1 = 1111 1011 0010

这个结果再与最初的值相与后, 只会有一位保留为1

0000 0100 1110 & 1111 1011 0010 = 0000 0000 0010

很显然, 这个值的与原值的末位0的个数是一致的

也就是说, 如果一个偶数, 在执行 x & -x的操作的时候, 最后结果肯定有如下两个特征

① 这个结果只有一位值是1, 其他位均是0

② 这个值的末位0的个数与原值保持一致

仔细一想, 这个原值肯定是能被结果值整除的, 而这个结果值又是2^ n, 那我们就可以描述成,

“当一个偶数与它的负值相与时, 结果是能整除这个偶数的最大的2的幂,

即: m = n & -n , 则 n % m = 0, 且 m = 2 ^ k”

所以当m=n时,可以用 n&-n == n 来判断n是不是2的整数次幂

2.x为奇数

当一个奇数 + 1时, 表示的二进制数则会发生进位, 这样的话, 会产生一个连锁反应,为奇数取反后的值一定是偶数,而 x与其取反的数相与结果肯定是0 ,但是由于相与的数是取反后再+ 1的值(肯定是个奇数), 也就是说, 只有最后一位有翻转,所以只有最后一位都是1, 相与结果仍旧是1, 而其他位所有的只都是相反值, 相与必为0 , 所以结论是:

“如果是x是奇数, 那x & -x 的结果一定是1”

(3)

易向以归宁🙄 2022-09-13

20220913235410_9553f9.jpg

(0)

Copyright 2016 - 2022 XUJC ACM Team
闽ICP备2020022076号-1