位运算

popcount类问题：
LC191 Number of 1 bits (Hamming Weight)
LC338 Counting bits
LC231 2的整数次幂 除了0和负数，(n & (n - 1)== 0)的是2的整数次幂。
⚠️LC477 汉明距离总和 统计每一位0或1的个数为t，总共有n个数，则该位贡献的汉明距离为t * (n - t)

异或：
LC421 数组中两个数的最大异或值
LC1310 子数组异或查询
LC1442 形成两个异或相等数组的三元组数目

异或找数：
LC136 Single Number全部与一下即可
LC137 Single Number II全部与，找一位是1的做partition，再分别与
LC260 Single Number III 统计每一位，mod3，再恢复
LC268 缺失的数字 原序列和[1…n]序列做位与

其他：
LC371 两整数之和
LC50 快速幂位与左移是进位，异或是不带进位的加法
LC190 Reverse Bits[32位都要与到]
⚠️LC201 数字范围按位与 右移到相等，再左移回来。
IP到CIDR

位运算基础

1. 对有符号整数右移>>：负数开头补1，正数开头补0

2. 异或运算xor 或 ^

   • 异或是不进位的加法。两个数位与左移一位是进位。
   • a == b <=> a xor b == 0
   • a xor b = c <=> b xor c = a <=> c xor a == b

3. n & (n -1) ：把这个数最后一位1变0

4. 运算符优先级问题，比如n & 1 == 0，因为==的优先级比&高， 导致了先计算了1 == 0，然后bool类型的隐式转换成了int，再做位与。参考C++ 运算符优先级, cppreference
5. 可以通过使用std::cout<<std::bitset<8 * sizeof(T)>(num_you_want_output_as_binary)的形式来实现二进制的输出
6. 要求好多数字的位运算结果时，可以尝试统计每一位的0或1的个数。

bitset

cppreference: bitset

std::bitset可以通过一个整数构造，也可以通过to_ulong()转换为一个整数。
std::bitset提供operator<<和to_string()，可以很方便地将一个数字以二进制形式输出。
std::bitset可以通过set()，reset()，flip()来调整某一位的值。
std::bitset提供所有逻辑运算符的重载。

---

LC784 字母大小写全排列

• 找到所有的字母，用std::array<char*, 12>将他们的指针与一个数字联系起来。顺便统计字母的数量n。
• 用一个n位二进制数来表示每一个字母是大小还是小写。
• 全排列即从0到2n所有的数。根据每一位是0还是1，来改变对应字母的大小写。

code

class Solution {
public:
    vector<string> letterCasePermutation(string S) {

        auto indices = array<char*, 12>{};
        // find all the letters in S, associate them with numbers
        auto letter_num = 0u;
        for(auto& c : S)
        {
            if(isalpha(c))
            {
                indices[letter_num++] = &c;
            }
        }

        // compute the maximum for an interger that has 'letter_num' bits
        const auto max = 1 << letter_num;

        auto res = vector<string>{};
        for(auto i = 0u; i < max; ++i)
        {
            auto bs = bitset<12>{i};
            for(auto j = 0u; j < letter_num; ++j)
            {
                // uppercase
                if(bs[j])
                {
                    auto c = toupper(*indices[j]);
                    *indices[j] = c;
                }
                // lowercase
                else
                {
                    auto c = tolower(*indices[j]);
                    *indices[j] = c;
                }
            }

            res.push_back(S);
        }

        return res;
    }
};

---

LC1239 串联字符串的最大长度

回溯。使用bitset<26>来记录每个英文字母出现与否。

code

class Solution {
public:
    vector<bitset<26>> mp;
    vector<int> mask;
    vector<string>* p_arr;
    int maxLength(vector<string>& arr) {
        mp = vector<bitset<26>>(arr.size(), bitset<26>{});
        mask = vector<int>(arr.size());
        p_arr = &arr;

        for(auto i = 0u; i < arr.size(); ++i)
        {
            for(auto c : arr[i])
            {
                // duplicate letters in arr[i]
                if(mp[i][c - 'a'])
                {
                    mask[i] = 1;
                }
                else
                {
                    mp[i].set(c - 'a');
                }
            }
        }

        return backtrace(0, 0, {});
    }

    auto backtrace(size_t cur, size_t len, bitset<26> bs) -> size_t
    {
        // cannot append more
        if(cur == mp.size())
        {
            return len;
        }

        // cur is masked or could lead to duplication, cannot append arr[cur]
        if(mask[cur]
        || (mp[cur] & bs).any() )
        {
            return backtrace(cur + 1, len, bs);
        }

        return max
        (
            // append cur
            backtrace(cur + 1, len + p_arr->at(cur).size(), bs | mp[cur]),
            // not append cur
            backtrace(cur + 1, len, bs)
        );
    }
};

popcount类问题

popcount，即统计一个二进制数中置为1的bit个数。

确认只有一个1

LC231 2的整数次幂
二的整数次幂的二进制形式必然只有一位是1，因此一个简单的想法是用 (n & (n - 1)) == 0 来判断，但是要注意几个边界情况：

• n < 0，2的整数次幂不会是负数
• n == 0，0不是2的整数次幂。

code

class Solution {
public:
    bool isPowerOfTwo(int n) {
        return n <= 0 ? false : (n & (n - 1)) == 0;
    }
};

统计共有几个1

Leetcode 191, Leetcode 338, 剑指Offer 15

思路：用这个数和它与1的差做与运算，会消去最后的1。这么做直到该数为0，统计这样做的次数。

• 时间复杂度是 O(k), k是这个二进制数中1的个数。
• 空间复杂度为 O(1)
• N & (N - 1) 可以把这个数最右边的1变为0

runtime count code

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int res = 0;
        for(;n;++res) n = n & (n - 1);
        return res;
    }
};

compile-time count

template <uint32_t N>
constexpr uint32_t hammingWeight = (hammingWeight<N & (N - 1)>) + 1;
template <> constexpr uint32_t hammingWeight<0> = 0;

其他思路：

SSE指令集 (gcc)

用gcc内置的__builtin_popcount(uint32_t)：

• 如果想让gcc编译器调用SSE4.2指令集的POPCNT ，要在前面加上
  #pragma GCC target("sse4.2")
• 时间复杂度：不知道，猜测也是 O(number of bits)
• 空间复杂度：O(1)

#pragma GCC target ("sse4.2")
class Solution {
public:
    vector<int> countBits(int num) {
        auto res = vector<int>{};
       res.reserve(num + 1);
        for(int i = 0; i <= num; ++i) res[i] = __builtin_popcount(static_cast<uint32_t>(i));
        return res;
    }
};

参考：
Function Specific Option Pragmas
Is builtinpopcount O(1) or O(log_2 k) ?
Bit Twiddling Hacks - Sean Eron Anderson

使用bitset头文件

std::bitset的count可以返回设置为true的位的数量。

C++20的bit头文件

template<class T>
constexpr int popcount(T x) noexcept;

统计每一位上的1的总数

LC477 汉明距离总和

可能会首先想到直接O(N^2)的复杂度计算所有元素之间的距离，这会导致直接超时。
巧妙的想法：统计每一位0或1的个数t，那么这一位贡献的汉明距离为t * (n - t)，n为nums数组中数字的个数。

code

class Solution {
public:
    int totalHammingDistance(vector<int>& nums) {
        int mask = 1;
        int res = 0;
        int size = nums.size();
        for(int i = 0, mask = 0; i < 32; ++i)
        {
            mask = mask == 0 ? 1 : mask << 1;
            int num = std::accumulate(nums.begin(), nums.end(),0, 
            [mask](int lhs, int rhs)
            {
                return lhs + ((rhs & mask) != 0 ? 1 : 0);
            });
            res += num * (size - num);
        }
        return res;
    }
};

异或

最大异或值

LC421 数组中两个数的最大异或值

• 只要求得到最大异或的值，不需要找到最大异或的两个数字。
• 高位上的1越多，值越大。
• 构造一个mask，这个mask用来提取nums中每个数字的前缀。
• 构造一个最大异或值的前缀res
• 将数组中的所有数字和mask做与，将前缀取出来，放到一个hashset当中。
• 假设res当前位为1，用res和数组中的每个数字的前缀做异或。检查得到的结果在hashset当中是否存在。
  • 如果存在，根据a xor b == c <=> b xor c == a，hashset中必然存在两个前缀使得该位为1。
  • 如果检查过所有的数字都不存在，则该位为0。
• 将mask变长1位，res往后挪一位。重复上述过程，直到res变为32位。
• res即为所求结果。

bitset code

class Solution {
public:
    int findMaximumXOR(vector<int>& nums) {
        // prefix-mask
        auto pmask = bitset<32>{};
        auto res = bitset<32>{};
        for(auto i = 31; i >= 0; --i)
        {
            pmask.set(i);
            
            auto pmap = unordered_set<uint32_t>{};
            // put all prefixes of nums into a hashset
            for(uint32_t n : nums)
            {
                pmap.insert(pmask.to_ulong() & n);
            }

            //assume that the i bit is 1
            auto pres = res;
            pres.set(i);

            //check if pres xor nums is in the hashset
            for(uint32_t n : nums)
            {                
                if(pmap.find(
                    (pmask.to_ulong() & n) ^  // prefix
                    pres.to_ulong())          // assumption
                != pmap.end())
                {
                    res = pres;
                    break;
                }
            }
        }

        return res.to_ulong();
    }
};

code

class Solution {
public:
    int findMaximumXOR(vector<int>& nums) {
        // prefix-mask
        auto pmask = 0;
        auto res = 0;
        for(auto i = 31; i >= 0; --i)
        {
            pmask |= (1 << i);
            
            auto pmap = unordered_set<uint32_t>{};
            // put all prefixes of nums into a hashset
            for(uint32_t n : nums)
            {
                pmap.insert(pmask & n);
            }

            //assume that the i bit is 1
            auto pres = res;
            pres |= (1 << i);

            //check if pres xor nums is in the hashset
            for(uint32_t n : nums)
            {                
                if(pmap.find((pmask & n) ^ pres) != pmap.end())
                {
                    res = pres;
                    break;
                }
            }
        }

        return res;
    }
};

异或前缀和

LC1310 子数组异或查询

构造异或的前缀和数组。

code

class Solution {
public:
    vector<int> xorQueries(vector<int>& arr, vector<vector<int>>& queries) {
        auto psum = vector<int>{};
        partial_sum(arr.begin(), arr.end(), back_inserter(psum), 
            [](int lhs, int rhs){return lhs ^ rhs;});

        auto res = vector<int>{};
        transform(queries.begin(), queries.end(), back_inserter(res), 
        [&psum](const auto& query)
        {
            auto back  = query.back();
            auto front = query.front();
            if(front == 0)
            {
                return psum[back];
            } 
            else
            {
                return psum[back] ^ psum[front - 1];
            }
        });

        return res;
    }
};

LC1442 形成两个异或相等数组的三元组数目

a = arr[i] ^ arr[i + 1] ^ ... ^ arr[j - 1]
b = arr[j] ^ arr[j + 1] ^ ... ^ arr[k]

p_a = arr[0] ^ arr[1] ^ ... ^ arr[i]
p_b = arr[0] ^ arr[1] ^ ... ^ arr[j]

如果a == b，有a ^ b == 0，我们得到

arr[i] ^ arr[i + 1] ^ ... ^ arr[k] == 0

• 因此我们需要在arr上寻找异或为0的子数组。考虑构造arr的异或前缀和：
  • 如果m < n且m和n两个位置的异或前缀和p_m和p_n相等，则有p_m ^ p_n == 0，p_m ^ p_n刚好是m和n之间的，异或为0的子数组。
  • 如果p_m == 0，则从0到m之间的也存在一个异或为0的子数组。
• 找到所有这样的子数组(m, n)，在(m, n]之间的任何一个数字和m,n都可以构成一个三元组。因此，这个题目变为求所有这样的子数组的长度和。

code

template<typename It>
auto range_num(It first, It last) -> size_t
{
    auto res = 0ul;
    for(;first != last; ++first)
    {
        for(auto e = first + 1; e < last; ++e)
        {
            res += *e - *first - 1;
        }
    }
    return res;
}

class Solution {
public:
    int countTriplets(vector<int>& arr) {
        // make an xor partial sum array
        auto xor_sum = vector<int>{};
        // to make the computation of length for all subarrays like (0, m], insert a 0 to the beginning.
        xor_sum.push_back(0);
        partial_sum(arr.begin(), arr.end(), back_inserter(xor_sum), [](auto lhs, auto rhs)
        {
            return lhs ^ rhs;
        });

        // associate each xor partial sum result with its position
        auto counter = unordered_map<int, vector<size_t>>{};
        for(auto i = 0u; i < arr.size() + 1; ++i)
        {
            counter[xor_sum[i]].push_back(i);
        }

        // compute the sum of lengths of all subarrays.
        auto res = 0ul;
        for(auto& pair : counter)
        {
            if(pair.second.size() > 1)
            {
                sort(pair.second.begin(), pair.second.end());
                res += range_num(pair.second.begin(), pair.second.end());
            }
        }

        return res;
    }
};

异或找数

缺失的数字

LC268 Missing Number.

Given an array containing n distinct numbers taken from 0, 1, 2, …, n, find the one that is missing from the array.

要求：线性时间复杂度，常数空间复杂度
利用XOR的思想，设数组中的数字为$a_i$，$i = 0, 1, \cdot, (n - 1)$，missing number 为$m$,那么我们有

$$(a_0 \text{ xor } 0 ) \text{ xor } (a_1 \text{ xor } 1) \text{ xor } \cdots \text{ xor } (a_{n-1} \text{ xor } (n-1)) \text{ xor } n$$

其中在$[0, n]$之间的整数都会因为异或而变为$0$, 剩下$0 \text{xor} m = m$，就找到了missing number.

另一个缺失的数字问题[LC1060 有序数组上缺失的数字]。给定的数组是一个有序数组，利用有序性，可以使用二分查找， 见二分查找

code

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int res = 0;
        int i = 0;
        for(; i < nums.size(); ++i)
            res = res ^ i ^ nums[i];
        return res ^ i;
    }
};

2xN + 1

• 简单的版本LC136 Single Number，数组中其他数字都出现了两次，可以直接把数组中所有数字都XOR，剩下的就是单独出现的数字了

code

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int result = nums[0];
        for(size_t i = 1; i < nums.size(); ++i){
            result ^= nums[i];
        }
        return result;
    }
};

3xN + 1

再复杂一点的就是LC137 Single Number II，每个数字都出现了3次。这个时候就不能用XOR了，我们需要设计个vector来统计所有数字中每一位1出现的个数。因为所有其他数字都出现了三次，那么在这一位上，所有其他数字1出现的个数也是3的倍数。这样我们就可以对每一位都mod 3，如果mod的结果是1，那么那个Single Number那一位就是1，否则就是0。之后使用这个数组还原single number即可。

code

inline constexpr static const size_t INT32_BITS = sizeof(int) * 8;

auto get_bits(int num, array<size_t, INT32_BITS>& bits)
{
    for(auto i = 0u; i < INT32_BITS; ++i)
    {
        auto mask = 1u << i;
        if(num & mask)
        {
            ++bits[i];
        }
    }
}

class Solution {
public:
    int singleNumber(vector<int>& nums) {

        auto bits = array<size_t, INT32_BITS>{};

        for(auto num : nums)
        {
            get_bits(num, bits);
        }

        for_each(bits.begin(), bits.end(), [](auto& n)
        {
            n %= 3;
        });

        auto res = 0;

        for(auto i = 0u; i < bits.size(); ++i)
        {
            if(bits[i])
            {
                res |= (1u << i);
            }
        }

        return res;
    }
};

2xN + 1 + 1

最复杂的就是LC260 Single Number III，这个题目里面有两个出现一次的，其他出现两次。我们按照最简单的[LC136 Single Number]的思路，把数组里面的数字先都XOR一下，这样我们就得到了两个出现一次的数字的XOR的结果。现在的问题是：怎么利用【XOR的结果】 和 【数组】 来还原这两个Single Number呢？
剑指Offer 56里提供的方案是，用xor结果里第一个为1的位作为标志(bitMask)，将数组分为两部分。 出现了两次的数字，因为其在(bitMask)这一位上必然是相同，也就会被分到同一组中。而不同的两个数字，在(bitMask)上必然是不同的，也就被分开了。之后在两组上再做xor，就得到那不同的那两个数字了。

code版本一

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        auto allXor = numsXor(nums.begin(), nums.end());
        uint32_t bitMask = 1;
           
        while((allXor & 1) == 0){
            allXor  = allXor  >> 1;
            bitMask = bitMask << 1;
        }

        auto tmpIt = partition(nums.begin(), nums.end(), [bitMask](int num){
            return num & bitMask;
        });
               
        return {numsXor(nums.begin(), tmpIt), numsXor(tmpIt, nums.end())};   
    }
    
    template<typename It>
    int numsXor(It first, It last){
        int result = 0;
        for(;first != last;++first) result ^= *first;
        return result;
    }
};

code版本二

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {

        auto xor_operator = [](int sum, int rhs)
        {
            return sum ^ rhs;
        };

        int xorAll = accumulate(nums.begin(), nums.end(), 0, xor_operator);

        int mask = 0;

        for(;;)
        {
            mask = mask == 0 ? 1 : mask << 1;
            if (xorAll & mask) break;
        }

        auto it = partition(nums.begin(), nums.end(), [mask](int x)
        {
            return (x & mask);
        });

        int num1 = accumulate(nums.begin(), it, 0, xor_operator);
        int num2 = accumulate(it, nums.end(), 0, xor_operator);

        return {num1, num2};
    }
};

其他

用异或交换两个数

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

不实用的方法，不但比直接交换慢，而且如果交换的是同一个数引用，会导致这个数清零。具体可见利用异或方式交换两个变量值的原理是什么？

位运算实现加法

见数学类问题#基本运算##位运算实现加法

快速幂

见数学类问题#基本运算##快速幂

翻转二进制数

LC190 Reverse Bits

code

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        //定义两个mask，一个最高位为1，另一个最低位为1
        uint32_t mask   = 1 << 31;
        uint32_t mask2 = 1;
        uint32_t res = 0;
        //为什么是32? 因为我们要在32位的每一位上执行一次
        for (int i = 0; i < 32; ++i)
        {
            //检查当前n的这一位，是不是1
            if (n & mask)
            {
                res |= mask2;
            }
            //mask往右移动
            //mask2往左移动
            //这样就实现了反转
            mask >>= 1;
            mask2 <<= 1;
        }
        return res;
    }
};

数字范围按位与

LC201 数字范围按位与

两个数字m,n, m <= n的二进制有两种情况：

• n的二进制比m多一位：比如n = 1000和m = 0100，那么由0100变化到1000的过程中，m的所有位都会有变化，导致与的结果必然为0
• n和m二进制位数一样多
  不断同时右移n和m直到n和m相等，变化只会发生在这两个相等的后面，因此将后面补零即可
  m = 1000, n = 1100 —> 相等的是最高位的1，过程中所有数:1000->1001->1010->1011->1100

code

class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        int shift = 0;
        // this contains two situations
        // m has the same num of digits as n --> m and n will be 0 
        // m has different same num of digits with n --> move to the lowest common digits
        while(m != n)
        {
            m >>= 1;
            n >>= 1;
            ++shift; 
        }
        return m << shift;
    }
};

IP到CIDR

LC751 IP 到 CIDR

• CIDR块的大小一定是2的整数次幂
• 每次从当前的ip位置取出一个CIDR块，CIDR块的大小受两个因素限制：
  • 当前ip的最低bit
  • 当前剩余的n的数量
• 如何找到当前合适的CIDR块？
  • 找到当前ip的最低bit，记其为第cidr位，则cidr_size = 1 << cidr是最大的cidr的CIDR块大小。
  • 比较cidr_size和n，如果cidr_size > n，我们必须得减小CIDR块的大小，直到(1 << cidr) < n。
• 找到合适的cidr后，生成字符串auto res = ipv4_ntoa(ip) + "/" + to_string(32 - cidr);
• 从n中减掉CIDR块的大小1 << cidr，在ip上加上CIDR块的大小1 <<cidr。
• 重复以上两步，直到n == 0。

code

#include <arpa/inet.h>

auto ipv4_aton(const char* addr) -> uint32_t
{
    auto res = in_addr{};
    ::inet_aton(addr, &res);
    return ntohl(res.s_addr);
}

auto ipv4_ntoa(uint32_t ip) -> string
{
    auto addr = in_addr{.s_addr = htonl(ip)};
    auto pstr = ::inet_ntoa(addr);
    return string{pstr};
}

auto ip_get_cidr(uint32_t& ip, uint32_t& n) -> string
{
    auto mask = 1u;
    auto cidr = 0u;
    while(true)
    {
        if(mask >= n || ip & mask)
        {
            break;
        }
        ++cidr;
        mask <<= 1;
    }

    while(mask > n)
    {
        --cidr;
        mask >>= 1;
    }

    auto res = ipv4_ntoa(ip) + "/" + to_string(32 - cidr);

    ip += (1 << cidr);
    n  -= (1 << cidr);

    return res;
}

class Solution {
public:
    vector<string> ipToCIDR(string ip, uint32_t n) {
        if(n == 0) 
        {
            return {};
        }

        auto cur_ip = ipv4_aton(ip.c_str());
        auto res = vector<string>{};

        while(n)
        {
            res.push_back(ip_get_cidr(cur_ip, n));
        }

        return res;
    }
};