We read every piece of feedback, and take your input very seriously.
To see all available qualifiers, see our documentation.
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
这真可以说是一个老朋友了,在不同的地方见过了好多次,只是我每次看见它,都得查一查它到底是什么意思,而且每次它的含义都还有点不同。这次看《剑指 offer》,作者讲解的比较清楚,所以我在这里顺便记录一下。
如果整数不为 0 ,则它的二进制表示中,至少有一位得是 1 。假设这个 1 位于最右侧,那么减去 1 之后,最右侧就变成了 0 。然后如果最右侧不是 1 ,而是 0 ,假设最右边的 1 位于第 m 位,那么减去 1 之后,第 m 位就变成了 0 ,然后 m 位之后的 0 全部变成了 1 。比如 1100 ,减去 1 之后,就变成了 1011 。
0
1
m
1100
1011
n - 1 的作用,是把最右边的 1 变成了 0 (其再右侧的 0 变成了 1),左边的所有位都保持不变。接下来,我们把 n - 1 和 n 按位取与运算(n & (n - 1)),那么在左边全部不变的前提下,右边的那些刚才从 0 变成 1 的位又回到了 0 的状态。比如 1100 ,减去 1 变成了 1011 ,然后 1100 & 1011 是 1000。所以,把一个整数减去 1 再与自己按位取与,会把该整数的最右边的 1 变成 0。
n - 1
n
n & (n - 1)
1100 & 1011
1000
题目:输入一个整数,输出该整数二进制表示中 1 的个数
这个题目不难,最不济就依次和 1 做按位与,然后右移,再按位与... 每次按位与之后看一下结果是不是 1 。这个解法的循环次数与输入的二进制表示长度有关系,结合我们上面的 n & (n - 1) ,我们可以有如下解法:
int countOf1(int n) { int count = 0; while (n != 0) { count++; n = n & (n - 1); } return count; }
上面的解法中,每次都把 n 的最右边的 1 变成了 0 ,直到 n 自己变成 0 ,那么变了几次,就说明 n 的二进制表示里就有几个 1 。
题目:输入一个正整数,判断该正整数是否是 2 的整数倍
这个题目也不难,可以不停地通过除以 2 看余数是否为 0 来判断,但是这样需要计算的次数也和输入的大小有关系。从二进制的角度考虑,一个数是不是 2 的整数倍其实就是它的二进制表示是不是只有一位为 1 ,如果是,那它就是 2 的整数倍,否则就不是。基于这个认知,加上 n & (n - 1) 把一个数的二进制表示的最右边的 1 变成 0 ,我们可以构思如下算法:
2
boolean isPowerOf2(int n) { return (n & (n - 1)) == 0; }
如果一个数把最右边的 1 变成 0 之后,就彻底变成了 0 ,那么这个数的二进制表示就只有一个 1 ,即它肯定是 2 的整数倍。
https://stackoverflow.com/questions/4678333/n-n-1-what-does-this-expression-do
The text was updated successfully, but these errors were encountered:
No branches or pull requests
这真可以说是一个老朋友了,在不同的地方见过了好多次,只是我每次看见它,都得查一查它到底是什么意思,而且每次它的含义都还有点不同。这次看《剑指 offer》,作者讲解的比较清楚,所以我在这里顺便记录一下。
先看 n - 1
如果整数不为
0
,则它的二进制表示中,至少有一位得是1
。假设这个1
位于最右侧,那么减去1
之后,最右侧就变成了0
。然后如果最右侧不是1
,而是0
,假设最右边的1
位于第m
位,那么减去1
之后,第m
位就变成了0
,然后m
位之后的0
全部变成了1
。比如1100
,减去1
之后,就变成了1011
。再看 n & (n - 1)
n - 1
的作用,是把最右边的1
变成了0
(其再右侧的0
变成了1
),左边的所有位都保持不变。接下来,我们把n - 1
和n
按位取与运算(n & (n - 1)
),那么在左边全部不变的前提下,右边的那些刚才从0
变成1
的位又回到了0
的状态。比如1100
,减去1
变成了1011
,然后1100 & 1011
是1000
。所以,把一个整数减去1
再与自己按位取与,会把该整数的最右边的1
变成0
。应用场景 1 ——计算一个数的二进制表示中有几个 1
这个题目不难,最不济就依次和
1
做按位与,然后右移,再按位与... 每次按位与之后看一下结果是不是1
。这个解法的循环次数与输入的二进制表示长度有关系,结合我们上面的n & (n - 1)
,我们可以有如下解法:上面的解法中,每次都把
n
的最右边的1
变成了0
,直到n
自己变成0
,那么变了几次,就说明n
的二进制表示里就有几个1
。应用场景 2 —— 判断一个正整数是不是 2 的整数倍
这个题目也不难,可以不停地通过除以
2
看余数是否为0
来判断,但是这样需要计算的次数也和输入的大小有关系。从二进制的角度考虑,一个数是不是2
的整数倍其实就是它的二进制表示是不是只有一位为1
,如果是,那它就是2
的整数倍,否则就不是。基于这个认知,加上n & (n - 1)
把一个数的二进制表示的最右边的1
变成0
,我们可以构思如下算法:如果一个数把最右边的
1
变成0
之后,就彻底变成了0
,那么这个数的二进制表示就只有一个1
,即它肯定是2
的整数倍。参考
https://stackoverflow.com/questions/4678333/n-n-1-what-does-this-expression-do
The text was updated successfully, but these errors were encountered: