15.md

二进制中1的个数

题目

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

示例

• 输入：10
• 返回值：2
• 说明：十进制中10的32位二进制表示为0000 0000 0000 0000 0000 0000 0000 1010，其中有两个1

思路

• n&(n-1)会把n最右边的1变成0，那么有多少个1就需要多少次这样的运算

前情提要

• 在二进制码中，为了区分正负数，采用最高位是符号位的方法来区分，正数的符号位为0、负数的符号位为1
• 剩下的就是这个数的绝对值部分，可以采用原码、反码、补码3种形式来表示绝对值部分
• 正数的反码就是其原码，补码也一样
• 负数的反码就是将原码除符号位以外每位取反，补码是其反码+1
• 计算机中二进制都是以其补码形式存放的

位移

• 左移运算 x << n 等价与 x 乘以 2 的 n 次方
• 右移运算 x >> n 等价与 x 除以 2 的 n 次方

异或

• 两个值相异结果为真

实现

func NumberOf1(n int) int {
	cnt := 0
	// 对负数的处理
	if n < 0 {
		// 获取负数的补码
		n = n & 0xffffffff // 11111111111111111111111111111111
	}
	// fmt.Printf("%b\n", 0xffffffff) // 16进制: f == 1111
	for n != 0 {
		n = n & (n - 1)
		cnt++
	}
	return cnt
}