[剑指Offer]二进制中1的个数

题目描述

输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。

解题思路

  1. 问题的关键点在于对于正数,如何得到它的二进制表示;对于负数,如何得到它的补码。负数在计算机中的二进制表示(原码、反码与补码)
  2. 在Python中,进制转换的函数为:bin()(转换为二进制),oct()(转换为八进制),hex()(转换为十六进制),int()(转换为十进制)。各个进制的表示开头为:0b(二进制),0o(八进制),0x(十六进制)。
  3. 在计算机中,所有的数字都是使用补码存储起来的。由于Python没有位数这个概念,所以得到二进制表示需要多一点操作,即将位数限制在32位,通过和一个32位的全1数字按位与运算即可。对于正数来说,上面的按位与操作可以不做,因为正数的符号位为0,补码即原码,所以前面的数字全为0,按位与没有意义。但对于负数来说,直接bin(-3)是不能得到其补码的,而是得到了3的原码前面加上了负号,即-0b11。则通过和一个32位的全1数字按位与运算可得到其补码(按位与运算把符号位的1视为了数字)。
  4. 这个32位的全1数字可写为0xffffffff0o377777777770b111111111111111111111111111111114294967295

代码

Python(2.7.3)

  1. 因为bin()输出为str格式,所以可以通过.count()来计数。

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

    运行时间:22ms
    占用内存:5756k

  2. 对于一个二进制数n,可以发现将其和n-1做按位与运算的结果是将n的二进制最右边的一个1变成了0,其它所有未变。故可以通过此方法循环来计算二进制中1的数量。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    # -*- coding:utf-8 -*-
    class Solution:
    def NumberOf1(self, n):
    # write code here
    if n < 0:
    n &= 0xffffffff
    count = 0
    while n:
    count += 1
    n &= n - 1
    return count

    运行时间:31ms
    占用内存:5840k

    参考

    AlgorithmsByPython-二进制中1的个数
    https://www.zhihu.com/question/314455297
    https://blog.csdn.net/leonliu06/article/details/78685248