C/C++ 位操作

关于位操作的几个术语：

• 设置（set）：将数二进制的某一位置 1
• 清除（clear）：将数二进制的某一位 1 清除，变为 0

将数字的二进制某一位置 1

• 首先将 1 左移 n 位
• 然后将结果与数字进行或（|）操作

#include <iostream>

void set(int& num, int n) {
    num |= 1 << n;
}

int main() {
    int num = 2;  // 0010
    int n = 2;  // 将第 2 位（0 开始）置 1
    set(num, n);  // 0110
    std::cout << num << std::endl;
}

清除数字的二进制某一位（置 0）

• 首先将 1 左移 n 位
• 然后对上面的结果取反（~）
• 然后与数字进行与（&）运算

#include <iostream>

void unset(int& num, int n) {
    num &= (~(1 << n));
}

int main() {
    int num = 6;  // 0110
    int n = 2;  // 将第 2 位（0 开始）清除
    unset(num, n);  // 0010
    std::cout << num << std::endl;
}

切换第 n 位

即将第 n 位的 1 变为 0，0 变为 1。

• 先将 1 左移 n 位
• 然后进行异或（^）操作

#include <iostream>

void toggle(int& num, int n) {
    num ^= (1 << n);
}

int main() {
    int num = 6;  // 0110
    int n = 2;  // 将第 2 位反转
    toggle(num, n);  // 0010
    std::cout << num << std::endl;
}

第 n 位是否被设置

将数字与 1 左移 n 位的结果进行与（&）操作

#include <iostream>


bool isSetNth(int num, int n) {
    return num & ( 1 << n);
}

int main() {
    int num = 6;  // 0110
    int n = 2;  // 第 2 位是否设置
    std::cout << std::boolalpha << isSetNth(num, n) << std::endl;
    return 0;
}

将数变成相反数

将数取反然后加 1 （反码加 1）

#include <iostream>

void toOpposite(int& num) {
    num = (~num + 1);
}

int main() {
    int num = -6;  // 1111....1010 (前面均为 1)
    toOpposite(num);  // 0000....0110
    std::cout << num << std::endl;
    return 0;
}

清除将最低位的 1

X = X & (X - 1)，例如：1000 = 1100 & 1010

#include <iostream>

void stripLastSetBit(int& num) {
    num &= (num - 1);
}

int main() {
    int num = 6;  // 0110
    stripLastSetBit(num);  // 0100
    std::cout << num << std::endl;
    return 0;
}

获取最低位为 1 的位

X = X & (-X)，例如:

  00101100
& 11010100
-----------
  00000100

#include <iostream>

int lowerSetBit(int num) {
    return num & (-num);
}

int main() {
    int num = 6;  // 0110
    std::cout << lowerSetBit(num) << std::endl;  // 0010
    return 0;
}

将第 i 位到最低位全部置 0

x &= ~((1 << i + 1) - 1)

#include <iostream>
#include <bitset>

int clearith2LSB(int num, int i) {
    return num & ~((1 << i + 1) - 1);
}

int main() {
    int num = 29;
    std::cout << "Before: " ;
    printWithBit(num, 2);

    std::cout << "After:  " ;
    printWithBit(clearith2LSB(num, 3), 2);
    return 0;
}

/*output:
    Before: 00011101
    After:  00010000 */

将最高位到第 i 位全部置 0

x &= (1 << i) - 1

#include <iostream>
#include <bitset>

void printWithBit(int num, int k) {
    if (k == 1) {
        std::cout << std::bitset<4>(num) << "\n";
    } else if (k == 2) {
        std::cout << std::bitset<8>(num) << "\n";
    } else if (k == 3) {
        std::cout << std::bitset<12>(num) << "\n";
    } else if (k == 4) {
        std::cout << std::bitset<16>(num) << "\n";
    }
}

int clearHSB2ith(int num, int i) {
    return num & (1 << i) - 1;
}

int main() {
    int num = 29;
    std::cout << "Before: " ;
    printWithBit(num, 2);

    std::cout << "After:  " ;
    printWithBit(clearHSB2ith(num, 3), 2);
    return 0;
}
// output
//  Before: 00011101
//  After:  00000101

大写字母转小写字母

ch |= ' ' 或 ch |= (1 << 5), ' ' 为 00100000

大写字母和小写字母对应的 bit 位 如下：

A -> 01000001          a -> 01100001
B -> 01000010          b -> 01100010
C -> 01000011          c -> 01100011
  .                               .
  .                               .
Z -> 01011010          z -> 01111010

可以看到对应的大小写字母之间除了第 5 位（100000，即 ' '字符）外是相同的，所以大写转小写只需要将第 5 为置 1，小写转大写将第 5 位置 0 即可。

也可以直接使用 cctype 文件中的 tolower

#include <iostream>
// #include <cctype>

void upperToLower(std::string& s) {
    for (auto& c: s) {
        c |= (1 << 5);
        // tolower(c);
    }
}

int main() {
    std::string s = "aBcDeFgHiJkLmN";
    std::cout << "Before: " << s << '\n';
    upperToLower(s);
    std::cout << "After : " << s << '\n';
    return 0;
}

// Output:
//  Before: aBcDeFgHiJkLmN
//  After : abcdefghijklmn

小写字母转大写字母

ch &= '_' 或 ch |= ~(1 << 5), '_' 为 11011111

也可以直接使用 cctype 文件中的 toupper

#include <iostream>
// #include <cctype>

void lowerToUpper(std::string& s) {
    for (auto& c: s) {
        c &= ~(1 << 5);
        // toupper(c);
    }
}

int main() {
    std::string s = "aBcDeFgHiJkLmN";
    std::cout << "Before: " << s << '\n';
    lowerToUpper(s);
    std::cout << "After : " << s << '\n';
    return 0;
}

// Output:
//     Before: aBcDeFgHiJkLmN
//     After : ABCDEFGHIJKLMN

大写转小写同时小写转大写

要将一个字符串中的大小写字母格式互换，即大写字母转成小写字母，并且小写字母转成大写字母，直接将 bit 位第 5 位反转即可。

ch ^= (1 << 5)

#include <iostream>

void changeStrLowerUpper(std::string& s) {
    for (auto& c: s) {
        c ^= (1 << 5);
    }
}

int main() {
    std::string s = "aBcDeFgHiJkLmN";
    std::cout << "Before: " << s << '\n';
    changeStrLowerUpper(s);
    std::cout << "After : " << s << '\n';
    return 0;
}

// Output:
//     Before: aBcDeFgHiJkLmN
//     After : AbCdEfGhIjKlMn

计算数字 bit 位中 1 的个数

Brian Kernighan’s Algorithm

1  Initialize count: = 0
2  If integer n is not zero
    (a) Do bitwise & with (n-1) and assign the value back to n
        n: = n&(n-1)
    (b) Increment count by 1
    (c) go to step 2
3  Else return count

#include <iostream>
#include <bitset>

void printWithBit(int num, int k) {
    if (k == 1) {
        std::cout << std::bitset<4>(num) << "\n";
    } else if (k == 2) {
        std::cout << std::bitset<8>(num) << "\n";
    } else if (k == 3) {
        std::cout << std::bitset<12>(num) << "\n";
    } else if (k == 4) {
        std::cout << std::bitset<16>(num) << "\n";
    }
}

int countBitOf1(int num) {
    int count = 0;
    while (num) {
        num &= num - 1;
        count++;
    }
    return count;
}

int main() {
    int num = 29;
    std::cout << "bits of num: ";
    printWithBit(num, 2);
    std::cout << "Count of 1: " << countBitOf1(num) << '\n';

    return 0;
}

// Output:
//     bits of num: 00011101
//     Count of 1: 4

计算 1 ~ n 的异或值

Number Binary-Repr  XOR-from-1-to-n
1         1           [0001]  <----- Always 1 as for n%4 = 1
2        10           [0011]  <----- n + 1
3        11           [0000]  <----- We get a 0
4       100           [0100]  <----- Equals to n
5       101           [0001]
6       110           [0111]
7       111           [0000]  <----- We get 0
8      1000           [1000]  <----- Equals to n
9      1001           [0001]
10     1010           [1011]
11     1011           [0000] <------ We get 0
12     1100           [1100] <------ Equals to n

int computeXOR(int n) {
    if (n % 4 == 0)
        return n;
    if (n % 4 == 1)
        return 1;
    if (n % 4 == 2)
        return n + 1;
    else
        return 0;
}

和与异或相等问题

给定一个正整数 n，找到正整数 i 的计数，使得 0 <= i <= n 且 n + i = n ^ i

Example

Input  : n = 7
Output : 1
Explanation:
7^i = 7+i holds only for only for i = 0
7+0 = 7^0 = 7


Input n = 12
Output: 4
12^i = 12+i hold only for i = 0, 1, 2, 3
for i=0, 12+0 = 12^0 = 12
for i=1, 12+1 = 12^1 = 13
for i=2, 12+2 = 12^2 = 14
for i=3, 12+3 = 12^3 = 15

So n + i = n ^ i implies n & i = 0

Hence our problem reduces to finding values of i such that n & i = 0. How to find count of such pairs? We can use the count of unset-bits in the binary representation of n. For n & i to be zero, i must unset all set-bits of n. If the kth bit is set at a particular in n, kth bit in i must be 0 always, else kth bit of i can be 0 or 1

Hence, total such combinations are 2^(count of unset bits in n)

For example, consider n = 12 (Binary representation : 1 1 0 0).

All possible values of i that can unset all bits of n are 0 0 0/1 0/1 where 0/1 implies either 0 or 1. Number of such values of i are 2^2 = 4.

#include <iostream>
#include <bitset>
#include <cctype>

void printWithBit(int num, int k) {
    if (k == 1) {
        std::cout << std::bitset<4>(num) << "\n";
    } else if (k == 2) {
        std::cout << std::bitset<8>(num) << "\n";
    } else if (k == 3) {
        std::cout << std::bitset<12>(num) << "\n";
    } else if (k == 4) {
        std::cout << std::bitset<16>(num) << "\n";
    }
}

int countValues(int n) {
    // unset_bits keeps track of count of un-set
    // bits in binary representation of n
    int unset_bits = 0;
    while (n) {
        if ((n & 1) == 0)
            unset_bits++;
        n = n >> 1;
    }
    // Return 2 ^ unset_bits
    return 1 << unset_bits;
}

int main() {
    int num = 29;
    std::cout << "bits of num: ";
    printWithBit(num, 2);
    std::cout << "Count of 1: " << countBitOf1(num) << '\n';

    return 0;
}

快速交换两个数

a ^= b;
b ^= a;
a ^= b;

#include <iostream>

void swap(int& a, int& b) {
    a = a ^ b;
    b = a ^ b;
    a = a ^ b;
}

int main() {
    int a = 5, b = 9;
    std:: cout << "a = " << a << " b = " << b << '\n';
    swap(a, b);
    std:: cout << "a = " << a << " b = " << b << '\n';

    return 0;
}