二进制检查操作

Question

假设class有n个学生要参加考试
我们打算设计出最快的方法来查明是否所有学生都参加了考试。
由于状态存储在存储库中 - 读取和更新操作很昂贵。
这可能通过位 shifting/toggling.
如果n=5，初始状态是n个字节的0 - 00000
每个完成考试的学生从右开始推1。

 00001
 00011
 00111

......

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

Answer 1

您已完成所有步骤：

n bits of 0:

status = 0

Each student completing the exam pushes 1 ,starting from right.

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

All bytes composed of 1 indicates closure.

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

Is there a more efficient way to achieve this?

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

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

此存储将占用 lg(n) 位而不是 n 位。在任何一种情况下，每个接受者都会有 load/modify/test/store 个周期，因此没有显着的时间节省。我能想到使用位域的唯一原因是，如果您担心一个人可能会参加两次测试并打乱您的计数。