3 ms·
> You can distinguish full and empty using x-y=0 vs x-y=N if the length N is a power of two Why wouldn't this work for, e.g., N=13?
by adwn 3y ago
> You can distinguish full and empty using x-y=0 vs x-y=N if the length N is a power of two
Why wouldn't this work for, e.g., N=13?
- simias 3y agoThe trick with powers of two is that you can just look at the MSB of `x XOR y` where x and y have one more bit than necessary to store the size. So for instance if you have a buffer with 8 entries you have a read pointer and a write pointer, both wrapping at 16 (4bits). When you address the buffer you ignore the MSB, when you want to test for empty you do `read == write`, when you want to test for full you do `read XOR write == 0b1000`. So you only have extremely cheap comparisons, bitwise XOR and counter increments to implement all operations.