首页 > 代码库 > 【C语言】练习2-9

【C语言】练习2-9

2024-07-07 20:14:06   226人阅读

  •  题目来源：《The C programming language》中的习题P38
  •  练习2-9：  在求对二的补码时，表达式x &= (x-1)可以删除x中最右边值为1的一个二进制位。请解释这样做的道理。用这一方法重写下面的bitcount函数，以加快其执行速度。
#include<stdio.h>

void main(){
    unsigned x = 0645;     // 110_100_101
    int a = bitcount(x);
    printf("%d\n",a);
}

/*bitcount:获得x（二进制）中1的个数*/
int bitcount(unsigned x){
    int b = 0;
    for(;x != 0; x >>= 1){
        if(x & 1){
            b++;
        }
    }
    return b;
}

　　解题思路：对于x的二进制形式，分为两种：最右边二进制位为0和最右边二进制位为1　

  1. 如果x的形式如XXX1, 那么x & （x-1）应该为 XXX0 & XXX1 = XXX0。 例如: 110_100_101 & 110_100_100 = 110_100_100。最右边的1被删除。
  2. 如果x的形式如XX10..00, 那么x & （x-1）应该为 XX01..11 & XX10..00 = XX00..00例如： 110_100_100 & 110_100_011 = 110_100_000。最右边的1被删除。

　　代码实现：

#include <stdio.h>
void main()
{
     unsigned x = 0645;     // 110_100_101
     int count = 0;
     while (x != 0) {
          x &= (x-1);
          count++;
     }
     printf("1-bit count: %d\n", count);
}

　　参考资料：http://blog.csdn.net/dc_726/article/details/7032656

 


联系
我们