[基础算法](6)位运算

引言:

位运算可他麻痹的是个好东西,通过 与 或 非 异或 左移 右移 可完成很多意想不到的事情,到特别适用于状态压缩,这章节会持续更新例题~

二进制中1的个数

模板题:801. 二进制中1的个数 - AcWing题库

image-20210711014255699

核心思路:

不断右移 每一位上 & 1 计数即可

代码:

#include<stdio.h>
#include<stdlib.h>
#define N 100000
int nums[N];
int main(){
    int n,res=0;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
       scanf("%d",&nums[i]);
       
    for(int i=0;i<n;i++){
        while(nums[i]){
            if(nums[i]&1) res++;
            nums[i]=nums[i]>>1;
        }
        printf("%d ",res);
        res=0;
    }
    
    return 0;
}

lowbit做法

使用lowbit操作,每次截取一个数字最后一个1后面的所有位,每次减去lowbit得到的数字,直到数字减到0,就得到了最终1的个数

lowbit原理
根据计算机负数表示的特点,如一个数字原码是10001000,他的负数表示形势是补码,就是反码+1,反码是01110111,加一则是01111000,二者按位与得到了1000,就是我们想要的lowbit操作

代码:

#include<iostream>
using namespace std;
int lowbit(int x){
    return x&(-x);
}
int main(){
    int n;
    cin>>n;
    while(n--){
        int x;
        cin>>x;
        
        int res=0;
        while(x) x-=lowbit(x),res++;

        cout<<res<<' ';
    }
    return 0;
}

本文链接:

https://nullcode.fun/163.html
1 + 9 =
快来做第一个评论的人吧~