C语言程序设计100例之（26）：二进制数中1的个数
例26 二进制数中1的个数
问题描述
如果一个正整数m表示成二进制，它的位数为n（不包含前导0），称它为一个n位二进制数。所有的n位二进制数中，1的总个数是多少呢？
例如，3位二进制数总共有4个，分别是4（100）、5（101）、6（110）、7（111），它们中1的个数一共是1＋2＋2＋3=8，所以所有3位二进制数中，1的总个数为8。
输入格式
一个整数T，表示输入数据的组数，接下来有T行，每行包含一个正整数 n（1<=n<=20）。
输出格式
对于每个n ，在一行内输出n位二进制数中1的总个数。
输入样例
3
1
2
3
输出样例
1
3
8
（1）编程思路1。
对于输入的n，n位二进制数m是位数为n并且首位为1的二进制数，且满足：
字符串截取20位 2n-1 ≤ n位二进制数m < 2n
因为首位为1，n位二进制数的个数就是n-1位的0和1的组合数，即2n-1个。
第1位必须为1，所以第1位的1的个数为2n-1个。
其他n-1位，总位数为(n-1)* 2n-1。其中0和1的个数是一半对一半，所以1的个数为(n-1)* 2n-1/2。
合计1的位数为：2n-1 +(n-1)* 2n-1/2。
因此，n位二进制数中1的个数直接用上式计算出来。计算时，用移位运算来计算2的n次方是一种快速的计算方法。
即n位二进制数中1的个数为 ：1<<(n-1)+(n-1)*(1<<(n-2))。
（2）源程序1。
#include <stdio.h>
int main()
{
int t,n;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
int ans=(1<<(n-1))+(n-1)*(1<<(n-2));
printf("%d\n",ans);
}
return 0;
}
（3）编程思路2。
设数组元素f[i]的值表示i位二进制数中1的个数。因为i位二进制数可以看成是i-1位二进制数的每个数在其最右边分别加上1或0得到的。因此，i位二进制数中1的个数一定是i-1位二进制数中1的个数的二倍，再加上i-1位二进制数的个数（因为每个数最右边如果加上1，1的个数会增加1个，加上0不会增加）。
即 f[i]=2*f[i-1]+2i-2
初始时，f[1]=1， f[2]=2*f[1]+2^0=3 。
（4）源程序2。
#include <stdio.h>
int main()
{
int f[21]={0,1};
for(int i=2;i<=20;i++)
{
f[i]=2*f[i-1]+(1<<(i-2));
}
int t,n;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
printf("%d\n",f[n]);
}
return 0;
}
习题26
26-1 1的个数相同
问题描述
给定一个大于0的整数n，把它转换为二进制，则其二进制数中至少有1位是“1”。编写一个程序，出比给定的整数n大的最小整数m。要求m和n两个整数转换成二进制数后，二进制数中包含的1的个数相同。
例如，120的二进制数为01111000，则比120大且二进制数中1的个数相同的最小整数为135（10000111）。
输入格式
输入包含若干组数据。每组数据是一个整数 N （1<=N <=65535）。N = 0 时输入结束。
输出格式
对于每组数据，在单独的一行输出一个整数m。
样例输入
92
120
0
样例输出
99
135
（1）编程思路1。
寻比n大的最小的整数m，最容易想到的方法是从n+1开始穷举。首先把十进制整数n转化为二进制，然后穷举比这个十进制整数大的数m，判断m和n两个数对应的二进制数中1的个数是否相同。判断的方法就是，把十进制数用n&1的位运算依次取出末位然后全部加起来，若两个数的所有二进制位加起来相等，则这两个数的二进制位一定有相同个1。
（2）源程序1。
#include <stdio.h>
int main()
{
int n,a,b,d,m;
while (scanf("%d",&n) && n!=0)
{
a=n; b=0;
while(a)
{
b+=a&1; a>>=1;
}
m=n;
do {
d=0; m++; a=m;
while(a)
{
d+=a&1; a>>=1;
}
} while(d!=b);
printf("%d\n",m);
}
return 0;
}
（3）编程思路2。
对十进制数n转化成的二进制数直接进行位变换，求出最小的整数m。
具体方法是：先到整数n对应的二进制数的最右边的1个1，从这个1开始，从右向左将连续出现的k个1变为0后，高1位的0变为1，再从最低位开始，将k-1个0变为1，即可得到最小的数n。
例如，32 对应的二进制数为00100000，将最右边的连续1个1变为0，高1位0变为1，即为01000000，对应整数为64。
又如，92 对应的二进制数为 01011100，将最右边的连续3个1变为0（得01000000），高1位变为1（得01100000），再将最低位的2（3-1）个0变为1，即为01100011，对应整数为99。
（4）源程序2。
#include <stdio.h>
int main()
{
int n,a,b,k,m;
while (scanf("%d",&n) && n!=0)
{
for (a=0; (n & (1<<a))==0; a++) ; // 到最右边的1个1所在位置a
for (b=a; (n & (1<<b))!=0; b++) ; // 到从a位开始向左的连续个1
m =n | (1<<b); // 把b位改成1
for (k=a; k<b; k++) m^=(1<<k); // 将从a位到b-1位的1全部取反变为0
for (k=0; k<b-a-1; k++) m |= 1<<k; // 将最低的b-a-1个位的0变为1
printf("%d\n",m);
}
return 0;
}
（5）编程思路3。
仔细琢磨整数的补码表示和位运算，可以将上面程序中的几个循环用一个表达式来完成。
1）按补码的表示法，正数的补码与原码相同，负数的补码是相应正数的补码的各位取反后加1。例如，以8位为例，32的补码是00100000，-32的补码是11100000；又如，92的补码是 01011100，-92的补码是 10100100。可以看出，把绝对值相等的正负两个整数用二进制数补码表示出来，从最低位开始到第1次出现1的地方为止，两者是一致的，高位部分的0和1恰好是相反的。利用这个特性，将正数m和相应的负数 –m进行逻辑与（&）的话，就能得到最初1出现的地方。
设x是整数n的二进制数保留最右边一个1，其余各位变为0后，所得到的数，则x = n&(-n)。
例如，n=92（01011100），则 -n=-92（10100100），x = n&(-n) = 01011100&10100100 = 00000100。
2）n＋x 是从右往左将整数n的第一个01转化为10。这是因为从最右边的一个1到第一个01，之间必然全是1，加上x后会一直进位，直到把01变为10，此时10的右边必然全是0。
例如，n=92，则 n+x=01011100 + 00000100=01100000。
3）表达式 n^(n+x) 可将整数n中最右边的第1个1开始，连续出现的1保留下来，且第1个01转
化成的10中的1也保留下来，其余位全部为0。 n/x可以去掉最右边的所有0。
例如，n=92，n^(n+x) = 01011100^01100000 = 00111100。
n^(n+x)/x = 00111100/00000100 =00001111。
即 n^(n+x)/x 相当将k+1（k为从整数n的最右边的1个1开始，从右向左连续出现的1的个数）个1全部右移到最右边，且左边全部清0。由于最右边只需将k-1个0变为1，因此，将n^(n+x)/x /4可以右移两位，去掉两个1。
4）n+x+(n^(n+x))/x/4就是所求的最小整数。
（6）源程序3。
#include <stdio.h>
int main()
{
int n,x,m;
while (scanf("%d",&n) && n!=0)
{
x=n&-n;
m= n+x+(n^(n+x))/x/4;
printf("%d\n",m);
}
return 0;
}
26-2 二进制
本题选自洛谷题库 （/problem/P2104）
题目描述
小Z最近学会了二进制数，他觉得太小的二进制数太没意思，于是他想对一个巨大二进制数做以下 4 种基础运算：
运算 1：将整个二进制数加 1
运算 2：将整个二进制数减 1
运算 3：将整个二进制数乘 2
运算 4：将整个二进制数整除 2
小Z很想知道运算后的结果，他只好向你求助。
（Ps：为了简化问题，数据保证+，-操作不会导致最高位的进位与退位）
输入格式
第一行两个正整数 n，m，表示原二进制数的长度以及运算数。
接下来一行 n 个字符，分别为‘0’或‘1’表示这个二进制数。
第三行 m 个字符，分别为‘+’，‘-’，‘*’，‘/’，对应运算 1，2，3，4。
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论