51dev.com IT技术开发者社区

51dev.com 技术开发者社区

leetcode-位1的个数(位与运算)

IT猿阅读(57)2020-01-03 收藏0次评论

位1的个数

编写一个函数,输入是一个无符号整数,返回其二进制表达式中数字位数为 ‘1’ 的个数(也被称为汉明重量)。

示例 :

输入: 11

输出: 3

解释: 整数 11 的二进制表示为 00000000000000000000000000001011

 

示例 2:

输入: 128

输出: 1

解释: 整数 128 的二进制表示为 00000000000000000000000010000000

需要了解的知识:

位运算符

位运算符作用于位,并逐位执行操作。&、 | 和 ^ 的真值表如下所示:

p

q

p & q

p | q

p ^ q

0

0

0

0

0

0

1

0

1

1

1

1

1

1

0

1

0

0

1

1

假设如果 A = 60,且 B = 13,现在以二进制格式表示,它们如下所示:

A = 0011 1100

B = 0000 1101

-----------------

A&B = 0000 1100

A|B = 0011 1101

A^B = 0011 0001

~A  = 1100 0011

下表列出了 C# 支持的位运算符。假设变量 A 的值为 60,变量 B 的值为 13,则:

运算符

描述

实例

&

如果同时存在于两个操作数中,二进制 AND 运算符复制一位到结果中。

(A & B) 将得到 12,即为 0000 1100

|

如果存在于任一操作数中,二进制 OR 运算符复制一位到结果中。

(A | B) 将得到 61,即为 0011 1101

^

如果存在于其中一个操作数中但不同时存在于两个操作数中,二进制异或运算符复制一位到结果中。

(A ^ B) 将得到 49,即为 0011 0001

~

按位取反运算符是一元运算符,具有"翻转"位效果,即0变成1,1变成0,包括符号位。

(~A ) 将得到 -61,即为 1100 0011,一个有符号二进制数的补码形式。

<<

二进制左移运算符。左操作数的值向左移动右操作数指定的位数。

A << 2 将得到 240,即为 1111 0000

>>

二进制右移运算符。左操作数的值向右移动右操作数指定的位数。

A >> 2 将得到 15,即为 0000 1111

将二进制数i与1相与,判断是否为1,然后将tag=1左移一位得到tag=2,然后再与i相与,循环结束的条件是tag==0;该算法时间复杂度为输入的i的位数。

public class ByteCompute {
public int byteCompute(int n){
int tag=1;
int count=0;
while(tag!=0){//由于int类型的函数是32位因此要循环32次
if((n&tag)!=0)
count++;
tag=tag<<1;
}
return count;
}

把一个整数n减去1,再和原来的整数与运算,会把该整数的最右边的1变成0,那么,一个整数的二进制中有多少个1,就可以进行多少次这样的操作。循环结束的条件是n为0;

public int byteCompute1(int n){
int count=0;
while(n!=0){//由于每次n和n-1相与都会导致,n的最右边的为1的元素变成0,因此总共要循环的次数就是1的个数次。
count++;
n=(n-1)&n;
}
return count;
}

 

以上就是leetcode-位1的个数(位与运算)的全部内容。

相关内容