剑指offer 二进制中1的个数

Posted on |

方法

方法1

一个整数减去1，在和原整数做与运算，会把该整数最右边的1变成0。那么一个整数的二进制表示有多少个1，就可以进行多少次这样的操作。

也就是整数的二进制有多少个1，就循环多少次。

1
2
3
4
5
6
7
8
9
10
11
# -*- coding:utf-8 -*-
class Solution:
    def NumberOf1(self, n):
        # write code here
        count = 0
        if n<0:
            n=n&0xFFFFFFFF #把负号去掉，如果负号在后面会陷入死循环
        while n:
            n = (n-1)&n
            count += 1
        return count

方法2：bin()函数将整数转换为二进制表示的字符串形式

1
2
3
4
5
6
7
8
9
# -*- coding:utf-8 -*-
class Solution:
    def NumberOf1(self, n):
        # write code here
        if n<0:
            s=bin(n&0xffffffff)
        else:
            s=bin(n)
        return s.count('1')

方法3

1
2
3
4
5
# -*- coding:utf-8 -*-
class Solution:
    def NumberOf1(self, n):
        # write code here
        return sum([(n>>i & 1) for i in range(0,32)])

补充知识

描述
bin() 返回一个整数 int 或者长整数 long int 的二进制表示。

语法
以下是 bin() 方法的语法:

1
bin(x)

参数
x — int 或者 long int 数字
返回值
字符串。

实例
以下展示了使用 bin 函数的实例：

1
2
3
4
>>>bin(10)
'0b1010'
>>> bin(20)
'0b10100'

关于位运算

1.与运算：A与B值均为1时，A、B与的运算结果才为1，否则为0 （运算符：&）

2.或运算：A或B值为1时，A、B或的运算结果才为1，否则为0 （运算符：|）

3.异或运算：A与B不同为1时，A、B的预算结果才为1，否则为0 （运算符：^）

4.按位翻转(按位取反)：将内存中表示数字的2进制数取反0取1，1取0 （运算符：~）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 判断一个数是不是2得整数次幂
def powerOf2(self, n):
    if n&(n-1) == 0:
        return True
    else:
        return False

# 判断两个数的二进制表示有多少位不一样, 直接比较两个数的二进制异或就可以
def andOr(self, m, n):
    diff = m^n
    count = 0
    while diff:
        count += 1
        diff = diff&(diff-1)
    return count
`