How can I do modulo with a bitmask in C?

Are you doing i % n, where n is a power of two? There’s a neat alternative way to do that: i & (n-1). See how it works by choosing n == 8, so i % 8 is the same as i & 7. 7 is 0b111, so i & 0b111 removes all but the three least significant bits. For instance, 14 % 8 == 6. But 14 & 7 == 0b1110 & 0b0111 == 0b0110 == 0b110 = 6.

For example, you might use this when implementing a ring buffer with power-of-two length.

Tagged #bitwise-operations, #optimization, #c, #programming.

Similar posts

More by Jim

Want to build a fantastic product using LLMs? I work at Granola where we're building the future IDE for knowledge work. Come and work with us! Read more or get in touch!

This page copyright James Fisher 2016. Content is not associated with my employer. Found an error? Edit this page.