Stuffing a small int & a flag into a u32

1

Suppose we have an index that fits in a u27, and a flag that fits in a u5. We can store both in a u32 as either:

(index << 5) + flag
(flag << 27) + index

In practice, is there any advantage/standard for picking one over the other? [Context: compressing stuff in b tree nodes, so not using 2 u32 is important]

1 Like
2

You could do it without bit shifting, using u32 flags that are multiples of 227, combine them with | (bitwise or), and extract the values with & (bitwise and) and an appropriate mask. In that case, the representation would be the

(flag << 27) + index

version. Disclaimer: I don’t know about practical advantages/standards and don’t have any experience doing something like this myself.

1 Like
3

This is clever.

For extracting the lower k bits, for k < 32, do we do

... & ((1 << k) - 1)

or is there a more idiomatic way to do this ?

4

I’d assume your k is actually a constant? Then it doesn’t really matter how you calculate it, and I would maybe just put the mask in a const.

const LOWER_27_BITS: u32 = (1 << 27) - 1;

I’m personally not aware of any more idiomatic approach. You have to make sure to use 28 in the shift for getting 27 bits to be 1 use parentheses even though the shift is used somewhat like an exponential here, and exponentiation usually binds tighter than addition. Maybe it’s slightly less confusing to use 2.pow then…

const LOWER_27_BITS: u32 = 2_u32.pow(27) - 1;

Edit: I mean, you can also do it with a literal

const LOWER_27: u32 = 0b_00000111_11111111_11111111_11111111;

Edit2: You can also work with the “complement” of the 27 being 5 (i.e. the two add to 32):

const LOWER_27: u32 = !0 >> 5;

Again, I personally don’t know if any of these would be considered “most idiomatic”.

2 Likes
5

I like using enums for flags. You can use something like no_panic to make the test a compile time assert. I'd also have utility methods, etc.

There are a number of crates for this purpose too, but I haven't tried them yet.

1 Like
6

Actually you have to make sure to use 27 in the shift, your code will give you 28 ones.

2 Likes
7

Thanks, good catch. Makes sense now, thinking about it again. I've messed up my testing by forgetting the parentheses, so that the result of 1 << 28 - 1 looked closer to the correct anwer. But only because that's 1 << (28 - 1).

So the code I had wouldn't have given 27 ones or 28 ones but instead a single one followed by 27 zeroes.

8

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.