《剑指Offer》-08位运算

发表于 | 分类于

二进制中1的个数

题目描述
输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

1
2
3
4
5
6
7
8
9
10
11
12
function NumberOf1(n)
{
    // write code here
    var number=0;
    while(n!=0){
        if(n&1==1){
            number++;
        }
        n=n>>>1;
    }
    return number;
}

总结：
负数以正数的补码表示
原码：一个整数按照绝对值的大小转化成二进制的数
反码：将二进制数按位取反
补码：反码加 1

位运算—会先将值转换成二进制

&与
两位同时为“1”，结果才为“1”，否则为0

|或
或运算法则：两位其中一个为“1”，结果为“1”，否则为0

^异或
两位不同，结果为“1”，否则为0

<<右移运算符
将数值向左移动若干位，用0补足

>>右移运算符 >>>无符号右移
将一个运算对象的各二进制位全部右移若干位，正数左补0，负数左补1
4 >> 2 = 1;（100右移2位为001）
直观的理解为，对于正数来说，右1移相当于除以2（但效率比除法高）

补充：
有符号位移运算时如果数字为正数时位移后在前面补0，为负数时则在位移后在前面补1

思路：
将数值与1进行与（&）运算，若结果为1则表明该数二进制最低位为1，则计数+1，否则最低位为0；将该数进行无符号右移（>>>）

0%