归档 53

数学 17 算法 15 杂项 7 生活 6 题解 4 课内 2 小说 1 待做 1

281 字

1 分钟

5-位运算

2026-04-08

2026-04-24

算法

位运算#

格雷码#

正变换#

二进制数存在一一对应的关系

n \oplus (n >> 1)

假如低位是0，+1则只有最后一位变化，异或右移的本身时只有最后一位发生变化，假如低位是连续的k个1，那么从0计数，+1的话第k个位置会翻转，0-k-1会翻转变成0，由于前面相同，而紧接着前面的k位置一个为0一个为1，k-1位置由于k和k-1在+1的过程中各自都翻转了所以不变，0-k-1位置两个都是连续的相同所以也一样，只有第k个位置会发生变化，

逆变换#

1
int x = g;
2

3
for (; g; g >>= 1) x ^= g;
4

5
return x;

状态压缩#

//TODO

数位#

1-base即长度

10进制下有

n =a_na_{n-1}\ldots a_{i}\ldots a_2a_1

有

段	公式
$a_n\ldots a_{i + 1}$ (high)	$n / 10^i$
$a_{i-1}\ldots a_{1}$ (low)	$n \% 10^{i-1}$
$a_i$ (unit)	$n / 10^{i-1} \% 10$

位运算常用函数#

bit_width(x) = 1 + floor(log2(x))

1
int bit_width(unsigned x) {
2
  int res = 0;
3
  while (x) {
4
    ++res;
5
    x >>= 1;
6
  }
7
  return res;
8
}

lowbit(x) = x & -x

countr_zero(x) = bit_width(lowbit(x)) - 1

1
int countr_zero(unsigned x) {
2
  if (x == 0) return 32;
3
  return bit_width(x & -x) - 1;
4
}

文章分享

如果这篇文章对你有帮助，欢迎分享给更多人！

5-位运算

https://skaco2.com/posts/01-algorithm/5-位运算/

作者

SKACO2

发布于

2026-04-08

许可协议

CC BY-NC-SA 4.0

4-概率论

4-抽象代数

评论区

分享你的想法，与大家交流讨论

音乐

音乐