编程之美 - 负数的二进制转换

1 简介

int型整数有4个字节，每个字节8个bit，所以一共32位。

1. 负十进制整数计算二进制：去掉符号，转为二进制，取反，加1
2. 负二进制整数计算十进制：取反，加1，转为十进制

观察上表可知，可将负整数去掉符号后，减去1，再计算二进制后取反。

另外，

1. python中直接计算二进制的函数为：bin(),字符版的二进制计算十进制为:int(aString,2)

2. 关于位运算，python提供了以下方法：&(按位与)，

   (按位或)，^(按位异或)，~(按位取反)，»(右移运算)，«(左移运算)。优先级从高到低依次为：~, & , ^, |。

3. 关于>>与<<:实际上，将一个数左移几位，就相当于将这个数乘以2的几次幂。将一个数右移几位，就相当于将这个数除以2的几次幂:

>>> 1<<2
4
>>> 4>>2
1

1.1 题目

计算在一个 32 位的整数的二进制表式中有多少个 1.

2 实现

class Solution:
    # @param num: an integer
    # @return: an integer, the number of ones in num
    def countOnes(self, num):
        # write your code here
        calc_1 = 0
        flag = False
        if num < 0:
            flag = True
            num = abs(num) - 1
        while num > 0:
            if (num % 2) == 1:
                calc_1 += 1
            num = num // 2
        if flag:
            calc_1 = 32 - calc_1
        return calc_1

2.1 更为巧妙的方法

class Solution:
    def countOnes(self, num):
        count = 0
        while n != 0:
            n = n & n - 1
            count += 1
        return count

1. 如果n>0，正数的补码和原码一致

(1)当n为正奇数时(n的二进制表示的末位为1)：

n: xxxxxxxx1
n-1: xxxxxxxx0
n&(n-1): xxxxxxxx0
n&(n-1)相当于去掉n的二进制表示中最右边的一个1。

(2)当n为正偶数时(n的二进制表示的末位为0)：
n: xxxxx1000
n-1: xxxxx0111
n&(n-1): xxxxx0000
n&(n-1)相当于去掉n的二进制表示中最右边的一个1。

2. 如果n<0

(3)当n为负奇数时，比如-1：
n=-1: 1111
n-1=-2: 1110
n&(n-1): 1110
n&(n-1)相当于去掉n的二进制补码中最右边的一个1。

(4)当n为负的偶数时，比如-2：
n=-2: 1110
n-1=-3: 1101
n&(n-1): 1100
n&(n-1)相当于去掉n的二进制补码中最右边的一个1。

3. 如果n=0

(5) 当n=0时:
n=0: 0000
n-1=-1: 1111
n&(n-1): 0000
n&(n-1)相当于去掉n的二进制补码中最右边的一个1(或 不处理，因为0的二进制补码中没有1)。

如，9999的二进制表示为： 0010 0111 0000 1111，共8个1.

综上(1)、(2)、(3)、(4)、(5)可知，n&(n-1)等价于去掉有符号整数整数n的二进制补码中最右边的一个1，无论n为正、为负或为0 .

另一相关的位运算知识点： n&(n-1)==0 可以用来判断n是否为2的幂次方(即：n中除符号位以外只有一个1，其他bit均为0)