Bit Manipulation常用总结

2024-03-17 13:33:40

1.判断奇偶

奇偶数的特征：如果一个数是偶数，则对于其二进制来说，最低位肯定是0；如果一个数是奇数，则对于其二进制来说，最低位肯定是1，因为在二进制表示中，只有会产生1

所以可以利用这一特征来判断奇偶数

if(num&1 == 0)
{
    //偶数
}
else
{
    //奇数
}

2.消去一个数中的最低位

比如十进制数5(0101), 我们要消去其二进制中的最低位的1

则操作是 (5&4) = (0101 & 0100) = 0100,从而将最低位处的1消除

典型应用：统计一个数的二进制表示中有多少个1

    int hammingWeight(uint32_t n) 
    {
     
        int count = 0;
        while(n)
        {
            count++;
            n &= (n-1);
        }

        return count;
    }

3.将二进制数进行翻转操作

可以用到C++中的bitset，它是类似于一个数组的结构，其内部元素只能是0或1，且每一位只占1bit

bitset数组简介：

bitset<8> bitset1; //构造长度为4的bitset数组，每一位默认为0
bitset<8> bitset2(12); //构造长度为8的数组，并用12的二进制去初始化
//也可以用字符串来进行构造
string s = "11000";
bitset<8> bitset3(s);

//注：当bitset的长度大于初始化所用的二进制数长度时，则在前面用0补足
//而当初始化所用的二进制长度大于bitset长度时，对于整数则只取整数后面部分，对于字符串则只取字符串前面部分

//bitset数组支持类似数组的[]操作，可以看做数组进行处理
//bitset支持位运算的所有操作符


//bitset的属性
bitset<8> foo ("10011011");

    cout << foo.count() << endl;　　//5　　（count函数用来求bitset中1的位数，foo*有５个１
    cout << foo.size() << endl;　　 //8　　（size函数用来求bitset的大小，一共有８位

    cout << foo.any() << endl;　　//true　　（any函数检查bitset中是否有１
    cout << foo.none() << endl;　　//false　　（none函数检查bitset中是否没有１
    cout << foo.all() << endl;　　//false　　（all函数检查bitset中是全部为１

//bitset的类型转换函数
bitset<8> foo ("10011011");

    string s = foo.to_string();　　//将bitset转换成string类型
    unsigned long a = foo.to_ulong();　　//将bitset转换成unsigned long类型
    unsigned long long b = foo.to_ullong();　　//将bitset转换成unsigned long long类型

    cout << s << endl;　　//10011011
    cout << a << endl;　　//155
    cout << b << endl;　　//155

所有，进行二进制的反转就和数组的反转操作是一样的

    uint32_t reverseBits(uint32_t n) 
    {

        bitset<32> bit_set(n);
        int i = 0; 
        int j = 31;
        while(i < j)
        {
            bool tmp = bit_set[i];
            bit_set[i++] = bit_set[j];
            bit_set[j--] = tmp;
        }
        return (uint32_t) bit_set.to_ulong();
    }

4.不借助外部变量实现两个数的交换

常规的实现两个数的交换通常借助外部变量来实现，比如

int a = 1;
int b = 2;
//实现两个数的交换，借助外部变量c
int c = a; //c = 1
a = b;     // a = 2
b = c;    // b = 1

不借助外部变量可以通过异或来实现
int a = 1;
int b = 2;

a ^= b; // a = 1^2 = 3
b ^= a; // b = 2 ^ 3 = 1
a ^= b; // a = 3 ^ 1 = 2
//所以最后 a = 2; b = 1;实现了两者的交换

5.求一个数的相反数

由于补码原理，对一个数进行取反后+1就可以得到它的相反数

6.求一个数的绝对值

由于正数的绝对值是其本身，负数的绝对值是其相反数，所以只需要判定正负，然后进行操作即可

如何判断正负呢？

对于32位整数来言，最高位是符合位，1代表负数，0代表正数

int myabs(int num)
{
    int  flag = num >> 31;
    return flag == 0 ? num : ~num+1;
}

在此基础上可以进一步优化，由于一个数与0异或相当于其本身，而与-1异或相当于对本身进行取反操作，所以

int myabs(int num)
{
    int  flag = num >> 31;
    return (flag^num) - flag;//如果flag = 0,则返回 num本身，若flag=-1，则返回 ~num+1
}

码农公寓