imicola 二进制
二进制

二进制

628 字 · 约 2 分钟

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

法一: 从原理上获取

  • 一个数的二进制的计算可以通过将这个数反复整除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;
}
cpp

法二: 位运算

  • &(与运算) : 考虑两个数 a,ba,b ,当 a&ba \& b 时,实际上是其二进制位的比较,当 a,ba,b 某一个相同的二进制为都为 1 时,运算结果的该二进制位也为 1 ,否则为 0 .
  • 考虑任意一个 int 类型的正整数 kk ,当 k&1k \& 1 时,实际上得出的数是 kk 第0位二进制位的结果
  • 考虑 kk >> xx ,这个过程将 kk 二进制位向右移动 xx 位。此时结合上一条,我们便可以将 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;
    }
}
cpp

快速获取一个数二进制有多少个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;
}
cpp

获取二进制最低位 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;
}
cpp

最低位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;
}
cpp

某些特殊二进制数判断

判断数kk是不是2的幂次

思路:如果kk为2的幂次,则kk的二进制构造为:k2=10⋯0⏞nk_2 = 1\overbrace{0\cdots0 }^{n},则(k−1)2=1⋯1⏞n−1(k-1)_2 = \overbrace{1\cdots1}^{n-1} 使用 k & (k−1)k\, \&\, (k-1)检查是否为0即可

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

判断数kk是不是二进制全1数

某些特殊数下的特殊性质

当kk为2n2^n时

  • 若p<kp < k :
    • p⊕k=p+kp \oplus k = p+k
    • p & k=0p\ \&\ k = 0
    • p ∣ k=0p\ \mid \ k = 0
    • pmod  k=p &(k−1)p\mod k = p\,\&(k-1)
  • k & (k−1)=0k\ \& \ (k-1) = 0

当k=2n−1k = 2^n - 1时

  • 若p≤kp \leq k时
    • p⊕k=p−kp \oplus k = p-k
    • p &  k=p%(k+1)p\,\&\, k=p\%(k+1)

知识关联

1 反向链接 · 0 提及笔记
局部关系图谱 悬停高亮 · 点击跳转