剑指Offer - 九度1513 - 二进制中1的个数
2024-08-29 05:50:03
剑指Offer - 九度1513 - 二进制中1的个数
2013-11-29 23:35
- 题目描述:
-
输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。
- 输入:
-
输入可能包含多个测试样例。
对于每个输入文件,第一行输入一个整数T,代表测试样例的数量。对于每个测试样例输入为一个整数。
n保证是int范围内的一个整数。
- 输出:
-
对应每个测试案例,
输出一个整数,代表输入的那个数中1的个数。
- 样例输入:
-
3
4
5
-1
- 样例输出:
-
1
2
32
题意分析:
这题是《编程之美》的原题了,只需要了解两个很巧妙的位操作:x & (-x),x & (x - 1)。
x & (-x)是树状数组的lowbit操作,能取出x最低位的‘1’。
x & (x - 1)则正好去掉x最低位的‘1’。
要数出x中有多少个‘1’,只需要一个一个去掉直到x=0为止。时间复杂度O(log(x)),空间复杂度O(1)。
// 651827 zhuli19901106 1513 Accepted 点击此处查看所有case的执行结果 1020KB 350B 80MS
//
#include <cstdio>
using namespace std; int main()
{
int x;
int res;
int n;
int i; while(scanf("%d", &n) == ){
for(i = ; i < n; ++i){
scanf("%d", &x);
res = ;
while(x){
x = (x & (x - ));
++res;
}
printf("%d\n", res);
}
} return ;
}
最新文章
- 10月28日PHP基础知识测试题
- SHUTDOWN_MSG: Shutting down NameNode at java.net.UnknownHostException: xxx
- android第三方框架 xlistview 的使用
- 运用SET ANSI_PADDING OFF创建某个字段为自增列的表,以及插入数据
- ubuntu ipv6网络电视(avplay)
- [未完成]关于xml文件的解析
- android122 zhihuibeijing 新闻中心NewsCenterPager加载网络数据实现
- XML文档形式&;JAVA抽象类和接口的区别&;拦截器过滤器区别
- socket用法
- UC浏览器插件开发
- php一些函数及方法...
- 【分支结构】Jcc 的一些助记
- mongodb cxx driver学习
- java生成棋盘
- yum安装提示错误Thread/process failed: Thread died in Berkeley DB library
- 2016.6.17——Valid Parentheses
- android 监听Home键
- hashset和treeset的区别
- Android SDK Manager检查更新时遇到Failed to fetch URL xxxxxxx reason: Connection to xxxxxx的错误的解决办法!
- php如何优化压缩的图片
热门文章
- anaconda添加源(channels)
- April 27 2017 Week 17 Thursday
- IOS instancetype的使用好处
- WIN7如何在任务栏建立我的电脑的快捷图标
- 设有三个进程A、B、C,其中A与B构成一对生产者与消费者(A为生产者,B为消费者),共享一个由n个缓冲块组成的缓冲池;B与C也构成一对生产者与消费者(此时B为生产者,C为消费者)共享另一个由m个缓冲块组成的缓冲池。用P、V操作描述它们之间的同步关系。
- 关于IDataReader.GetSchemaTable的一些事情
- Spring boot 集成三种定时任务方式
- Java面试不得不知的程序(二)
- 概述「DAG加边至强连通」模型&;&;luoguP2746校园网Network of Schools
- zabbix服务端安装配置