剑指 Offer 15. 二进制中1的个数
剑指 Offer 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'。
方法一:逐位判断
根据 与运算 定义,设二进制数字 n ,则有:
若n&1=0 ,则 n 二进制 最右一位 为 0 ;
若 n&1=1 ,则 n 二进制 最右一位 为 1 。
根据以上特点,考虑以下 循环判断 :
判断 n 最右一位是否为 1 ,根据结果计数。
将 n 右移一位(本题要求把数字 n 看作无符号数,因此使用 无符号右移 操作)。
算法流程:
初始化数量统计变量 res = 0。
循环逐位判断: 当 n = 0时跳出。
res += n & 1 : 若n&1=1 ,则统计数 resres 加一。
n >>= 1 : 将二进制数字 n无符号右移一位 。
代码:
class Solution {
public int hammingWeight(int n) {
int res = 0;
while(n != 0) {
res += n & 1;
n >>= 1;
}
return res;
}
}
方法二:巧用n&(n−1)
(n−1) 解析: 二进制数字 n 最右边的 1 变成 0 ,此 1 右边的 0 都变成 1 。
n&(n−1) 解析: 二进制数字 n 最右边的 1 变成 0 ,其余不变。
public class Solution {
public int hammingWeight(int n) {
int res = 0;
while(n != 0) {
res++;
n &= n - 1;
}
return res;
}
}
相关文章
- [视频教程] 最新版swoole安装和TASKS功能测试
- [操作系统]磁盘调度算法
- [操作系统]磁盘的物理结构
- [视频教程] 使用composer安装使用thinkphp6.0框架
- [视频教程] 配置mysql用户的权限并查询数据
- [视频教程] docker端口映射与目录共享运行PHP
- [操作系统]具有快表的内存转换机构
- [视频教程] ubuntu系统下安装最新版的MySQL
- [操作系统]内存非连续分配方式
- [PHP] 安装PHP报错“Primary script unknown”的解决方法
- [视频教程] ubuntu系统下安装最新版PHP7.3.X环境
- [操作系统]内存动态分区分配算法
- [操作系统]内存连续分配管理方式
- [视频教程] 如何在docker环境下的纯净ubuntu系统中安装最新版nginx
- [操作系统]内存覆盖与交换
- [操作系统]内存的基础知识
- 某业务自助开通账户问题排查
- [操作系统]处理机调度的概念和层次
- 将博客搬至CSDN
- 某业务付费统计脚本问题排查