【题解】An Easy Problem
2024-09-05 12:21:22
题目描述
给定一个正整数N,求最小的、比N大的正整数M,使得M与N的二进制表示中有相同数目的1。
举个例子,假如给定的N为78,其二进制表示为1001110,包含4个1,那么最小的比N大的并且二进制表示中只包含4个1的数是83,其二进制是1010011,因此83就是答案。
输入格式
输入若干行,每行一个数n(1≤n≤1000000),输入"0"结束。
输出格式
输出若干行对应的值。
输入样例
1
2
3
4
78
0
输出样例
2
4
5
8
83
题解
容易想到,当$n$加上$lowbit(n)$时,$1$的数量一定会减少$cnt$,我们只需要从末位开始找$cnt$个$0$位,将其改为$1$,得到的就是$m$了。
#include <iostream>
#include <cstdio> #define lowbit(x) ((x) & -(x)) using namespace std; int n, m;
int cnt; int main()
{
int tmp;
while(scanf("%d", &n) && n)
{
m = n + lowbit(n);
tmp = n;
while(tmp) ++cnt, tmp -= lowbit(tmp);
tmp = m;
while(tmp) --cnt, tmp -= lowbit(tmp);
tmp = ;
while(cnt)
{
if((tmp & lowbit(m)) ^ ) --cnt, m += tmp;
tmp <<= ;
}
printf("%d\n", m);
}
return ;
}
参考程序
最新文章
- 集成基于OAuth协议的单点登陆
- iOS 真机调试不能连接网络的排错过程
- \(\S1 \) Gaussian Measure and Hermite Polynomials
- ubuntu下firefox安装Adobe Flash Player
- android-satellite-menu
- Map的三种遍历
- cp 提示 overwrite 问题
- Spring Boot 配置优先级顺序
- html5 音频和视频(audio And video)
- CSS:a:link;visited;hover;active解释及正确顺序
- 0423上课练习(list、while、def)
- MySQL 基础知识梳理学习(二)----记录在页面层级的组织管理
- 使用tcpreply对DPDK进行压力测试(一台主机,2张网卡压测)
- c++ 计算cpu占用率
- Spring中的ThreadPoolTaskExecutor
- 57. 激活office时出下以下问题的解决方案
- (转)如何修改windows下mysql的字符集
- JSP的学习三(中文乱码)
- ubuntu16.4搭建tensorflow环境
- 关于React setState的实现原理(一)