目录

zrlong 的个人博客

希望大家都能保护好自己身上的特质,无论是五年还是十年,永远善良,不服输,热爱你所热爱。在漫长岁月的变迁里,是这些让你永远迷人,富有生命力。

X

又被妙到了之位运算

起因

今天写了一道分组位运算,让我再次感受到了位运算的奇妙。我整理的时候在想,会不会出现数组中有三个相同数的情况,整理完,我打开下一道题,真的是三个数的!这可把我难住了。我只想到了遍历,把所有出现的数的二进制各个数位相加,最后除以三取余。看到了别人的解析,我真是佩服的五体投地。

题目

剑指 Offer 56 - II. 数组中数字出现的次数 II - 力扣(LeetCode) (leetcode-cn.com)

在一个数组 nums 中除一个数字只出现一次之外,其他数字都出现了三次。请找出那个只出现一次的数字。

解析

有限状态自动机

二进制的各位进制规则相同,因此考虑一位就可以了。对于所有数字中的某二进制位 1 的个数,存在 3 种状态,即对 3 余数为 0, 1, 2。

  • 输入二进制位1,则状态按如下顺序转换

  • 输入二进制位0,则状态不变

    0120

ab00d4d1ad961a3cd4fc1840e34866992571162096000325e7ce10ff75fda770Picture2.png

一位二进制只能表示两种状态,因此我们需要二位二进制来表示三种状态。设高位为two ,低位为one。则状态转换为:

0a7ea5bca055b095673620d8bb4c98ef6c610a22f999294ed11ae35d43621e93Picture3.png

对于单个二进制位的位运算的一些特点:

  • 异或运算:x ^ 0 = xx ^ 1 = ~x
  • 与运算:x & 0 = 0x & 1 = x
  • ~0 = -1~1 = -21 & -1 = 11 & -2 = 0
计算one的方法:
if two == 0:
  if n == 0:
    one = one
  if n == 1:
    one = ~one
if two == 1:
    one = 0

引入异或运算,可以将其化简为:

if two == 0:
    one = one ^ n
if two == 1:
    one = 0

再引入与运算

one = one ^ n & ~two

f75d89219ad93c69757b187c64784b4c7a57dce7911884fe82f14073d654d32fPicture4.png

计算two的方法:

6ba76dba1ac98ee2bb982e011fdffd1df9a6963f157b2780461dbce453f0ded3Picture5.png

修改为新 one后,得到了新的状态图。观察发现,可以使用同样的方法计算 two ,即:

two = two ^ n & ~one
返回值:

以上是对数字的二进制中 “一位” 的分析,而 int 类型的其他 31 位具有相同的运算规则,因此可将以上公式直接套用在 32 位数上。

遍历完所有数字后,各二进制位都处于状态 00 和状态 01(取决于 “只出现一次的数字” 的各二进制位是 1 还是 0 ),而此两状态是由 one 来记录的(此两状态下 twos 恒为 0 ),因此返回 ones 即可。

代码:

class Solution {
    public int singleNumber(int[] nums) {
        int ones = 0, twos = 0;
        for(int num : nums){
            ones = ones ^ num & ~twos;
            twos = twos ^ num & ~ones;
        }
        return ones;
    }
}
二进制各位相加,取余
class Solution {
    public int singleNumber(int[] nums) {
    int res = 0;;
    int[] counts = new int[32];
    for(int i = 0; i < nums.length; i++) {
        for(int j = 0; j < 32; j++) {
            counts[j] += nums[i] & 1; // 更新第 j 位
            nums[i] >>>= 1; // 第 j 位 --> 第 j + 1 位
        }
    }
    for(int i = 0; i < 32; i++) {
        counts[i] %= 3; // 得到 只出现一次的数字 的第 (31 - i) 位 
    }
    for(int i = 0; i < counts.length; i++) {
        res <<= 1; // 左移 1 位
        res |= counts[31 - i]; // 恢复第 i 位的值到 res
    }
    return res;
    }
}

标题:又被妙到了之位运算
作者:zrlong
地址:http://blog.zrlong.top/articles/2022/04/12/1649768266444.html