二进制检查操作

Question

假设一个班级有n名学生参加考试。 我们打算以最快的方式找出所有学生是否参加过考试。 由于状态存储在存储库中 - 读取和更新操作很昂贵。 这可能通过位移/切换来实现。 如果n = 5，则初始状态为n个字节0 - 00000 每个完成考试的学生从右开始推动1。

 00001
 00011
 00111

......

由1组成的所有字节表示闭包。 我们如何使用位操作实现这一目标？ 有没有更有效的方法来实现这一目标？

Answer 1

你已经完成了所有步骤：

n位0：

status = 0

每个完成考试的学生从右开始推动1。

status = status << 1  # push previous to left
status = status | 1    # set the lowest bit

由1组成的所有字节表示闭包。

allOnes = (1<<num_students) -1
closure = (status == allOnes)

有没有更有效的方法来实现这一目标？

@Alain的评论是正确的：你描述的方法只是一种从1到n计数的内存效率较低的方法。为什么不使用简单的计数器呢？

takers +=1
completed = (takers == num_students)

对此的存储将采用lg（n）位而不是n位。在任何一种情况下，每个接受者都会有加载/修改/测试/存储周期，因此没有显着的时间节省。我可以想到使用位域的唯一原因是，如果你担心一个人可能会参加测试两次并甩掉你的计数。