大家好,又见面了,我是你们的朋友全栈君。
输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。
Python没有unsigned int类型,负数& 0xFFFFFFFF 返回的数就成一个正数 Python要使用 n & 0xffffffff 得到一个数的补码
思路一:位运算
(1)<< 左移运算符 将运算对象的 各二进制位 全部左移若干位:符号位不变,低位(右边)补 0
11 << 2 = 44
# 详细过程
00000000 00000000 00000000 00001011
<< 2
00000000 00000000 00000000 00101100 (因为最高位是0,它表示一个正数)
=
44
————————————
-14 <<2 =-56
# 详细过程
11111111 11111111 11111111 11110010 (-14的补码)
<< 2
11111111 11111111 11111111 11001000 (补码)
# 看上面的结果,符号位为1是负数,我们还要将它转换成 原码 才能计算出它的值
11111111 11111111 11111111 11001000 (补码)
11111111 11111111 11111111 11000111 (反码)
10000000 00000000 00000000 00111000 (原码)
# 所以最后结果为:
-56
左移,对于正数来说,左移多少位等于 乘以 2 ^ (左移位数);左移1 相当于乘以2(但效率比乘法高)
(2)>> 右移运算符 将运算对象的 各二进制位 全部 右移若干位:低位溢出,符号位不变,并用符号位补溢出的高位
4 >> 2 = 1
# 详细过程
00000000 00000000 00000000 00000100
>> 2
00000000 00000000 00000000 00000001(因为最高位是0,它表示一个正数)
# 所以最后结果为:
1
————————————
-14 >> 2 = -4
# 详细过程
11111111 11111111 11111111 11110010 (-14的补码)
>> 2
11111111 11111111 11111111 11111100 (补码)
# 看上面的结果,符号位为1是负数,我们还要将它转换成 原码 才能计算出它的值
11111111 11111111 11111111 11111100 (补码)
11111111 11111111 11111111 11111011 (反码)
10000000 00000000 00000000 00000100 (原码)
# 所以最后结果为:
-4
右移,对于正数来说,右移多少位等于 除以 2 ^ (右移位数);右移 1 相当于除以2(效率比除法高哦)
# 左移
class Solution:
def NumberOf1(self, n):
if n<0:
n = n & 0xFFFFFFFF
count=0
for i in range(32):
mask = 1 << i
if n & mask : # 注意这里不能写 成 if n & mask == 1 :
count+=1
return count
# 右移
class Solution:
def NumberOf1(self, n):
# write code here
if n<0:
n = n & 0xFFFFFFFF
count = 0
while n:
if n & 1 : # 或者写 if n & 1 ==1: 也行
count += 1
n = n >> 1 # 不断的重复右移一位
return count
判断次数更少,更快,更优的位运算解决方法
class Solution:
def NumberOf1(self, n):
if n < 0:
n = n & 0xFFFFFFFF
count = 0
while n:
count += 1 # 只要n不为0 就要记录一次,所以要写在前面,开始能进来就不为0
n = n & (n-1)
return count
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/145382.html原文链接:https://javaforall.cn