是否可以使用按位运算在随机 unicode 字符串中找到重复字符？

Question

我一直在寻找一种在字符串中查找重复字符的解决方案，我对按位运算的解决方案很感兴趣。

我发现了这样一个按位运算的变体。但在其中，搜索发生在 ASCII table.

的 a-z 范围内

func HasDuplicates(str string) (string, bool) {
    checker := 0
    for _, char := range str {
        val := char - 'a'
        fmt.Println(val)
        if (checker & (1 << val)) > 0 {
            fmt.Printf("'%c' is Duplicate\n", char)
            return str, false
        }
        checker |= 1 << val
    }
    return str, true
}

是否可以像上面的示例一样，仅针对随机 unicode 字符串（象形文字、表情符号等）制定通用解决方案？

Answer 1

使用 big.Int 作为位集：

func HasDuplicates(str string) (string, bool) {
    var bits big.Int
    for _, char := range str {
        val := int(char)
        fmt.Println(val)
        if bits.Bit(val) != 0 {
            fmt.Printf("'%c' is Duplicate\n", char)
            return str, false
        }
        bits.SetBit(&bits, val, 1)
    }
    return str, true
}

https://go.dev/play/p/kS-OxYPts5G

效率如何取决于 big.Int 的实现，您无法像对简单整数使用按位运算那样控制它。

您也可以使用布尔映射，尽管那样它就不再是按位运算了：

func HasDuplicates(str string) (string, bool) {
    var bits = make(map[int]bool)
    for _, char := range str {
        val := int(char)
        fmt.Println(val)
        if bits[val] {
            fmt.Printf("'%c' is Duplicate\n", char)
            return str, false
        }
        bits[val] = true
    }
    return str, true
}

是否可以使用按位运算在随机 unicode 字符串中找到重复字符？

Is it possible to find duplicate characters in a random unicode string using the bitwise operations?

go

bit-manipulation

bitwise-operators