位运算小技巧记录
本文最后更新于 574 天前,其中的信息可能已经有所发展或是发生改变。

位运算

主要记录一下平时遇到的一些使用位运算处理问题的小技巧,也许会不断更新把。。。

二进制枚举子集

对于用二进制表示的集合 x,如下方式可以枚举其每一个子集

for (int i = x; i; i = ((i - 1) & x)) {
    //TODO
}

Gosper's Hack

这个算法可以快速枚举一个 n 元集合中的 k 元子集

比如 n = 7, k = 4,那么最小的一个二进制数就是 0001111,最大的一个二进制数是1111000

那么我们需要枚举的就是 0001111 ~ 1111000 之间全部的 1 的个数为 4 的二进制数。

所以,我们需要做的是,从一个二进制数得到下一个数呢。比如上面的 0001111 -> 0010111 -> 0011011

而1的个数不能变,很容易想到,想要一个数变大,那么就把二进制位中的1,往左侧与更高位的0进行交换即可。那么如何保证变大的幅度最小呢?那就是在尽可能低的位进行这样的交换,总结下来就是如下两句话:

  • 从右往左,找到第一个 01,交换这两个位
  • 把第一个 01 右侧的全部 1,全部移动到最右侧

实现

首先是第一步:找到 01

int low_bits(int n) {
    return n & -n;
}

这个操作可以求得一个二进制数的从高位到低位的最后一个 1

这个 low_bits 可以帮助我们找到第一个 01,并交换他们。比如 x = 10110,其 lb = 00010,我们计算 x + lb = 11000。由于 lb 是最后一个 1,加上 lb 之后就能不断进位,直到把第一个 01 变为 10

接下来需要求解一下 01 右侧多少个 1,并且要把这些 1 全部放在最右侧。

由于 lbx 中最后一个 1,且 x + lb 后,会一直进位到遇到第一个 01。那么第一个 01 右侧的,就是 lb 最后一位 1 所在的位置,到第一个 010 所在的位置,中间的位数。

由于 x + lb 会从最后一个 1,一直进位到第一个 0,那么 xx + lb,在右侧第一个 1,和后续第一个 0 之间,都是相反数,而其他的位都相同,那么我们可以做一下异或,将 x 中右侧连续的 1 提取出来

x  =                       011001110
lb =                       000000010
x + lb =                   011010000
x ^ (x + lb) =             000011110
x ^ (x + lb) / lb =        000001111
x ^ (x + lb) / lb >> 2 =   000000011

上面就是一个例子,提取的结果就是 000011110,注意这里因为 0110 异或的原因,1 的数量多了两个,后续要移除两个。

这个数里所有的 1 还没有被移动到右侧,这里只需要除以 lb 即可,因为 lb 记录的就是第一个 1 的位置

最终,我们通过计算 x + lb 得到左侧的部分,通过 x ^ (x + lb) / lb >> 2 得到右侧部分,拼接起来即得到下一个数。

统计集合元素状态

这个说法其实有点模糊,因为我也不知道应该怎么描述,直接来看题吧

给你一个整数 n ,对于 0 <= i <= n 中的每个 i ,计算其二进制表示中 1 的个数 ,返回一个长度为 n + 1 的数组 ans 作为答案。

对于这道题来说,最简单的方法就是对每个 i 使用 i&(i-1)的方法统计数量。

如果想要达到 O(n) 的时间复杂度,就需要如下的方法

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> bits(n + 1);
        int highBit = 0;
        for (int i = 1; i <= n; i++) {
            if ((i & (i - 1)) == 0) {
                highBit = i;
            }
            bits[i] = bits[i - highBit] + 1;
        }
        return bits;
    }
};

对于每个数来说,我们可以在遍历过程中确定当前的最高位是多少,然后利用动态规划的思想,借助之前的结果快速计算。

其实思路还是很简单的,为什么我要把它写下来呢?

因为这让我想到了之前碰到的一道题 1655. 分配重复整数 ,其中也用到了这个思路,只是这时候的状态不是每一位是否为1,而是每一位对应的数组值,这样就可以快速得到每个集合对应的和。不过当时并没有想到这点。

reference

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇