创建整数数据结构并找出给定整数所在的组件

Question

我有一组 32 位整数，我将用它们制作一个数据结构，将这些整数放入不同的组件（如 dsu ），必须使用 按位和 ，如果两个整数的按位且不为零，则它们位于同一组件中，现在给定一个整数，我如何获得（假设已经为当前整数的前缀创建了数据结构）其中的组件这个整数会撒谎吗？例如说 [1,5,3,8] 被给定一组整数而不是 (1,5,8) 位于一个组件中，因为任何对的 lsb 将确保非零“位和”并且 (8) 将位于它自己的组件，或者很可能是完全不同的算法，如果你能想到的话，它会简单得多，

编辑：

然而，两个整数有可能有位和为零，但如果引入第三个整数，它有成对的位和非零，那么所有三个都将位于相同的组件 ex [2,12,6] 2 和 12 在操作上给出 0 但 2 和 6 没有，12 和 6 没有所以 6 将把所有三个统一在一个组件中。

编辑 2：我能想到一个天真的算法，它使用 32 个长度的数组，其中一个条目由类似结构的链表（如邻接列表）组成，即如果设置了第 i 个位，则索引我将包含第 i 个设置位的所有整数，但它可以给我 O(n) 搜索，我更倾向于 dsu，但发现很难创建它。

Answer 1

要求意味着传入的整数 x 应该与组件 C 连接当且仅当 x 的按位 AND 与 C) 是非零的。

disjoint-set 数据结构可以很好地解决这个问题。每个组件的 'root' 还可以维护其所有成员的按位或，这可以通过单独的哈希映射来完成，尽管这不是绝对必要的。

您还应该保留从每个 bit-position 到具有该 bit-position 集的组件（唯一，如果存在）的任何成员的哈希映射。当添加一个新的整数时，扫描它的所有 set-bits：使用这个 hashmap 来查找所有要合并的组件，或者是否创建一个新组件。这应该会提供几乎 constant-time 更新。任何时候最多也有 1 + ceil(log_2(M)) 个不同的组件，其中 M 是您见过的最大整数，最多为 33。

如果您想避免 Disjoint-Set 代码的某些复杂性，您可以使用 Paul Hankin's 组件列表的建议。根据您的编程语言以及您是否要计算重复项，组件可以表示为（位掩码、多重集）对，其中位掩码是所有成员的按位或，而成员的多重集允许您打印一个成员的所有成员组件和测试包含在 O(1) 时间内，尽管插入可能需要更长的时间（但摊销时间仍然不变）。

如果您永远不需要打印组件的成员或检查是否实际添加了特定整数，则只需存储位掩码就足够了。

Answer 2

下面是一些将组件表示为不相交位掩码列表的 go 代码 (runnable link)。先前看到的整数在它具有 non-zero 按位与（或零分量，如果它为零）的分量中。

可以使用新整数更新组件列表，方法是找到它具有 non-zero 按位 AND 的所有组件，并将它们替换为单个组件，即这些组件和新组件的按位或元素.

任何输入值中每位最多有一个分量，如果分量为零则加一。这里最多有 32 个分量，因为输入值规定为 32 位。

package main

import (
    "fmt"
)

// makeComponents returns a slice of disjoint bitmasks
// that represent the different components in the input.
func makeComponents(xs []uint32) []uint32 {
    var cs []uint32
    for _, x := range xs {
        j := 0
        for i, c := range cs {
            cs[j] = cs[i]
            if c & x != 0 || (x == 0 && c == 0) {
                x |= c
            } else {
                j++
            }
        }
        cs = append(cs[:j], x)
    }
    return cs
}

// component returns the component (from cs) that x is in.
func component(cs []uint32, x uint32) int {
    for i, c := range cs {
        if x==c || x & c != 0 {
            return i
        }
    }
    panic("no component")
}

// showComponents outputs the input values with those in the same
// component on the same line.
func showComponents(xs []uint32) {
    cs := makeComponents(xs)
    xperc := make([][]uint32, len(cs))
    for _, x := range xs {
        c := component(cs, x)
        xperc[c] = append(xperc[c], x)
    }
    for _, xc := range xperc {
        fmt.Println(xc)
    }
}

func main() {
    xs := []uint32{0, 1, 3, 6, 8, 16, 48, 65}
    showComponents(xs)
}

创建整数数据结构并找出给定整数所在的组件

Creating a data structure of integers and finding which component a given integer lies in

algorithm

bit-manipulation

graph-theory

disjoint-sets

data-structures