<>面试题15. 二进制中1的个数

请实现一个函数,输入一个整数,输出该数二进制表示中 1 的个数。例如,把 9 表示成二进制是 1001,有 2 位是 1。因此,如果输入 9,则该函数输出
2。

<>示例 1:

输入:00000000000000000000000000001011
输出:3
解释:输入的二进制串 00000000000000000000000000001011 中,共有三位为 ‘1’。

<>示例 2:

输入:00000000000000000000000010000000
输出:1
解释:输入的二进制串 00000000000000000000000010000000 中,共有一位为 ‘1’。

<>示例 3:

输入:11111111111111111111111111111101
输出:31
解释:输入的二进制串 11111111111111111111111111111101 中,共有 31 位为 ‘1’。

<>解题1

因为JDK中的Integer包装类中自带了toBinaryString方法,可以实现十进制转2进制。
可以先调用这个String s = Integer.toBinaryString(n);进行十进制转换成二进制
然后遍历一遍,匹配1。计数。就ok了。
但是效率有点低

import java.util.Arrays; class Solution { static public int hammingWeight(int n
) { int num = 0; String s = Integer.toBinaryString(n); for(int i = 0;i<s.length(
);i++){ if(s.charAt(i)=='1'){ num++; } } return num; } public static void main(
String[] args) { System.out.println(hammingWeight(11)); } }
<>解题思路2 利用“移位”操作实现

果然是十进制转换二进制的时候出了问题。
利用“移位”操作实现

import java.util.Arrays; class Solution { static public int hammingWeight(int n
) { int num = 0; for(int i = 31;i >= 0; i--) { if((n >>> i & 1)==1){ num++; } }
return num; } public static void main(String[] args) { System.out.println(
hammingWeight(11)); // System.out.println(); } }
<>利用“移位”操作实现

我们可以直接利用移位操作对一个十进制数进行移位操作,即:将最高位的数移至最低位(移31位),除过最低位其余位置清零,使用&
操作,可以使用和1相与(&),由于1在内存中除过最低位是1,其余31位都是零,然后把这个数按十进制输出;再移次高位,做相同的操作,直到最后一位
,代码如下。可以说,这是我到目前为止见到的最简单的实现方式了。
public void binaryToDecimal(int n){ for(int i = 31;i >= 0; i--) System.out.
print(n >>> i & 1); }

说明:由于计算机中存储的都是数的补码,正数的原码、反码、补码都是相同的;而负数的原码、反码、补码是不一样的,补码=原码取反+1(符号位不变)。所以,负数是按照它的补码输出的。

>>>为逻辑移位符,向右移n位,高位补0
>>算数移位符,也是向右移n位,不同的是:正数高位补0,负数高位补1
<< 移位符,向左移n位,低位补0

技术
©2019-2020 Toolsou All rights reserved,
vue的v-if与v-show的区别C语言控制台小游戏,打砖块用C++跟你聊聊“原型模式” (复制/拷贝构造函数)身价530亿美元!世界首富前妻再嫁化学老师:承诺捐赠一半财富关于过年ESP8266/ESP32 系统篇: 优化系统启动时间java简单的抽奖算法,抽奖Demo比特币站上5.2万美元 美团CEO王兴:理论上中本聪已经是世界首富了连 CEO 都不香了?这些互联网大佬接连辞任比尔·盖茨:疫情后彻底恢复正常可能要到2022年末