Get last k bits of a uN

x: uN;
let y = x & ((1 << k) - 1)

normally, I would write something like above, but:

  1. it is not as elegant compared to (x << k) or (x >> k)
  2. when k = N, this is annoying as we have to bump 1 up to higher bit, as it down after the -1

Is there a more elegant way to say 'keep the last k bits; zero all other bits' for uN ?

EDIT: it is okay if your technique only works for N = 8, 16, 32, 64

How about x & !x.checked_shr(k).unwrap_or(0).wrapping_shl(k)?

For 𝓀 ∈ [0..127], you can write this:

type INT = u...;
fn last_bits(x: INT, k: u32) -> INT {
    x & !(!0u128 << k) as INT
}

I prefer this way.

let y = (x << (N - k)) >> (N - k)
2 Likes

Another potential approach: x & !(uN::MAX.checked_shl(k).unwrap_or(0)).

You might consider looking at the canonical C expressions for the various things in x86 Bit manipulation instruction set - Wikipedia

Sounds like you're doing this one:

That is incorrect: it doesn't work for k = 0 (the shift by N - 0 overflows).

That exact expression doesn't work for the same reason (and is in fact mentioned in the OP): the shift overflows for k == N so you either have to handle that case specially, or it panics/produces an incorrect result.

The approved answer also panics in debug for k == 0 or produces an incorrect result in release for k > N, so I assumed that was fine. The check is also likely to be well-predicted, assuming that's it's normally in 1..N -- and that if it's not optimized out entirely because it's a constant.

Looks like there's an interesting LLVM behaviour here, actually. It recognizes x & ((1 << k)-1) as bzhi on its own, but not if it's guarded with an if k < u64::BITS check.

Godbolt for assembly-peeking a few different options: https://rust.godbolt.org/z/6b8zf3YYq

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.