关于二进制的常用代码（学习笔记）

大家好，欢迎来到IT知识分享网。

快速判断二进制中有几个1

方法1： 这里涉及一个&的知识点，&是按位与，就是在一位一位的做与运算， while(n>0) //这一句，当n不等于0的时候循环执行以下循环体，n等于0的变化条件在n>>=1这一句，将n左移一位，这样当n中所有的”1”位都移出时，就跳出循环了 { 
    if((n&1)==1) //这句逐个通过位与的方式查看当前n最左边的一位是不是1，若是，则n&1=1,c加1用来计数 c++; n>>=1; } return c;//这样循环结束时就能得到所需的1的个数了 需要注意的是循环条件这部分很巧妙，保证当n的右边没有1的时候就不做循环了，可以假设n=1，循环体就只执行一次就跳出了，而不用遍历n的每一位 方法2： x=x&(x-1) 表达式的意思就是:把x的二进制表示 从低位开始，将遇到的第一个为1的比特位 置0。 例如： e1: x = 0 x-1 = 0 x&(x-1)=0 e2: x = 0 x-1 = 0 x&(x-1)=0 在循环中利用该表达式可以快速的判断一个数的二进制中有多少个1。 int func(x) { 
    int countx = 0; while(x) { 
    countx ++; x = x&(x-1); } return countx; } x=x&(x-1)还可以快速判断x是不是2^n。当x为unsigned类型的变量，且其值为2的n次幂的时候，结果为零 

快速幂取模（防止爆ll）

LL mul(LL a,LL b) { 
    LL ans=0; while(b) { 
    if(b&1) ans=(ans+a)%p; a=(a+a)%p; b=b>>1; } return ans; } LL Pow(LL a,LL b) { 
    LL result=1; LL base=a%p; while(b) { 
    if(b&1) result=mul(result,base)%p; base=mul(base,base)%p; b=b>>1; } return result; }