资讯

精准传达 • 有效沟通

从品牌网站建设到网络营销策划,从策略到执行的一站式服务

计算二进制中1的个数

问题:计算某个数的二进制中1的个数

站在用户的角度思考问题,与客户深入沟通,找到龙江网站设计与龙江网站推广的解决方案,凭借多年的经验,让设计与互联网技术结合,创造个性化、用户体验好的作品,建站类型包括:成都网站建设、成都网站制作、企业官网、英文网站、手机端网站、网站推广、域名与空间、虚拟空间、企业邮箱。业务覆盖龙江地区。

思路:x = x & (x-1) 将 x 的二进制最右面的一个 1 变为 0,其余保持不变。反复操作,直到变为 0 为止,计算操作次数,即为 x 的二进制中 1 的个数。

证明:假设 x 的二进制末尾为 10...0 [末尾有 k 个 0,k = 0,1,2,...]。

则 x - 1 的二进制末尾 k+1 位为 01...1 [末尾有 k 个 1,k = 0,1,2,...],其他与 x 相同。

从而 x & (x-1) 的末尾 k+1 位为 00...0 [末尾有 k+1 个 0,k = 0,1,2,...],其他与 x 相同。

即 x = x & (x-1) 将 x 的最右边的一个 1 变为 0,其余位数无变化。

C++程序:

#include 
using namespace std;

int manyOne(int x){
    int countx = 0;
    while(x){
        ++countx;
        x = x&(x-1);
    }
    return countx;
}

int main(){
    cout<

类似问题:x = x | (x+1) 将 x 的二进制最右面的一个 0 变为 1,其余保持不变。

证明:假设 x 的二进制末尾为 01...1 [末尾有 k 个 1,k = 0,1,2,...]。

则 x + 1 的二进制末尾 k+1 位为 10...0 [末尾有 k 个 0,k = 0,1,2,...],其他与 x 相同。

从而 x | (x+1) 的末尾 k+1 位为 11...1 [末尾有 k+1 个 1,k = 0,1,2,...],其他与 x 相同。

即 x = x | (x+1) 将 x 的最右边的一个 0 变为 1,其余位数无变化。


应用:判断一个整数 x 是否为 2 的幂。

思路:假如 x 为 2 的幂,则 x 只有最高位为 1,其余均为 0,因此按照上面的做法 x = x & (x-1) 将会为 0;反之,假如 x = x & (x-1) 为 0,则 x 只有一位为 1,其余均为 0,显然 x 为 2 的幂。

C++程序:

#include 
using namespace std;
int isTwoPow(int x){
    if( (x&(x-1)) == 0) return 1;
    else return 0;
} 
int main(){
    cout<            
            
                        
文章题目:计算二进制中1的个数
当前地址:http://www.cdkjz.cn/article/jgpjsi.html
多年建站经验

多一份参考,总有益处

联系快上网,免费获得专属《策划方案》及报价

咨询相关问题或预约面谈,可以通过以下方式与我们联系

大客户专线   成都:13518219792   座机:028-86922220