二进制

数学 二进制 位运算

快速获取某一个数的二进制

法一: 从原理上获取

• 一个数的二进制的计算可以通过将这个数反复整除2且取模2来获得其位数，直到这个数变为0

#include <iostream>
#include <vector>
 
std::string decimalToBinary(int n) {
    if (n == 0) return "0";
    std::string binary;
    while (n > 0) {
        binary = (n % 2 == 0 ? "0" : "1") + binary;
        n /= 2;
    }
    return binary;
}
 
int main() {
    int number;
    std::cout << "请输入一个十进制数: ";
    std::cin >> number;
    std::string binaryForm = decimalToBinary(number);
    std::cout << "该数字的二进制表示为: " << binaryForm << std::endl;
    return 0;
}

法二: 位运算

• &(与运算) ： 考虑两个数 $a,b$ ,当 $a\&b$ 时，实际上是其二进制位的比较，当 $a,b$ 某一个相同的二进制为都为 1 时，运算结果的该二进制位也为 1 ，否则为 0 .
• 考虑任意一个 int 类型的正整数 $k$ ，当 $k\&1$ 时，实际上得出的数是 $k$ 第0位二进制位的结果
• 考虑 $k$ >> $x$ ,这个过程将 $k$ 二进制位向右移动 $x$ 位。此时结合上一条，我们便可以将 k 的每一位表示出来

#include <bits/stdc++.h>
 
std::vector<int> decimalToBinary(int n)
{
    std::vector<int> bit_2;
    for (int i = 31; i >= 0; i--) {
        bit_2.emplace_back((n >> i) & 1);
    }
    while (!*bit_2.begin()) bit_2.erase(bit_2.begin());
    return bit_2;
}
 
int main()
{
    int n;
    std::cin >> n;
    std::vector<int> ans = decimalToBinary(n);
    for (auto &&i : ans) {
        std::cout << i;
    }
}

快速获取一个数二进制有多少个0或1

放进函数里不断向右一位与 1 进行与运算，计数即可

#include <bits/stdc++.h>
 
int count_2bit(int n, bool x)
{
    int cnt = 0;
    while (n > 0) {
        if ((n & 1) == x) {
            cnt++;
        }
        n >>= 1;
    }
    return cnt;
}
 
signed main()
{
    //ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n;
    std::cin >> n;
    int onecount = count_2bit(n, 1);
    int zerocount = count_2bit(n, 0);
    std::cout << "count one = " << onecount << std::endl;
    std::cout << "count zero = " << zerocount << std::endl;
    return 0;
}

获取二进制最低位 1 / 0 在第几位

最低位 1

要快速找到一个数的二进制表示中最低位的1的位置，可以通过以下步骤：

• 找到最低位1：计算 n & -n，这会得到一个仅保留n最低位1的掩码。

• 位置确定：通过计算掩码的二进制位数或使用计数尾部零的函数（如__builtin_ctz）得到位置。

#include <bits/stdc++.h>
 
int get_2_low0(int n)
{
    if (n == 0) return -1;
    int mask = (n) & -(n);
    int res = __builtin_ctz(mask);
    return res;
}
 
int main()
{
    int n;
    std::cin >> n;
    std::cout << get_2_low0(n) << std::endl; // 输出0
    return 0;
}

最低位0

和取1类似，只需要取 ~n & -~n 即可然后找保留1的位置即可

#include <bits/stdc++.h>
 
int get_2_low0(int n)
{
    int mask = (~n) & -(~n);
    int res = __builtin_ctz(mask);
    if (pow(2, res) > n) return -1;
    return res;
}
 
int main()
{
    int n;
    std::cin >> n;
    std::cout << get_2_low0(n) << std::endl;
    return 0;
}

某些特殊二进制数判断

判断数$k$是不是2的幂次

思路：如果$k$为2的幂次，则$k$的二进制构造为：$k_2=1\stackrel{n}{\overbrace{0\cdots 0}}$,则$(k-1{)}_2=\stackrel{n-1}{\overbrace{1\cdots 1}}$ 使用 $k\&(k-1)$检查是否为0即可

• bool is_power_of2 = k & ( k - 1 ) == 0

判断数$k$是不是二进制全1数

• 结合上一个判断
  • bool is1num = k&(k+1) == 0

某些特殊数下的特殊性质

当$k$为$2^n$时

• 若$p<k$ :
  • $p\oplus k=p+k$
  • $p\&k=0$
  • $p\mid k=0$
  • $p\mathrm{mod}k=p\&(k-1)$
• $k\&(k-1)=0$

当$k=2^n-1$时

• 若$p\le k$时
  • $p\oplus k=p-k$
  • $p\&k=p\%(k+1)$