# Bit interleaving in std **URL:** \ **Category:** libs\ **Created:** [November 3, 2025, 11:44pm UTC](https://internals.rust-lang.org/t/bit-interleaving-in-std/23681 "2025-11-03T23:44:37Z")\ **Posts on this page:** 8\ **Page:** 1
**Author:** ![NyxCode](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/nyxcode/32/13374_2.png) [@NyxCode](https://internals.rust-lang.org/u/NyxCode)\ **Post date:** [November 3, 2025, 11:44pm UTC](https://internals.rust-lang.org/t/bit-interleaving-in-std/23681/1 "2025-11-03T23:44:37Z")
I'd like to see some utilities for interleaving bits of unsigned numbers in std. I first came across that operation when dealing with space filling curves, which are common in computer graphics, e.g. to construct quad/octrees. For morton/z-order curves, one takes the x and y (and z) components of a point, and interleaves the bits, yielding `... y1 x1 y0 x0` or `... z1 y1 x1 z0 y0 x0`. Bit interleaving makes an other appearance when constructing bayer matrices used for [ordered dithering](https://en.wikipedia.org/wiki/Ordered_dithering), as described [here](https://bisqwit.iki.fi/story/howto/dither/jy/#Appendix%202ThresholdMatrix). These are the two use-cases I came across, but I'm sure there are a lot more. [graphics.stanford.edu](https://graphics.stanford.edu/%7Eseander/bithacks.html#Interleave64bitOps) lists three ways of implementing this operation, with "Interleave bits by Binary Magic Numbers" seemingly being the most commonly used. All three algorithms listed there first "spread" the bits of the components, which are then or-ed together. Not listed there is the x86 `pdep` instruction of the BMI extension, which can do everything in one pass. Being much more general, I'd expect it to perform worse than the other algorithms, though i have not benchmarked anything. Therefore, my proposal would be to add the following to std: ```rust impl {u8, u16, u32, u64} { // spread bits apart, filling the integer with n 0-bits between every two bits. // overflowing bits are truncated. fn spread_bits(self, n: u32) -> B { .. } where B: "unsigned integer larger than Self" } ``` I'd appreciate feedback on the idea and API, as well as advice on what to do to actually get this into std. ---
**Author:** ![quaternic](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/quaternic/32/10440_2.png) [@quaternic](https://internals.rust-lang.org/u/quaternic)\ **Post date:** [November 4, 2025, 12:19am UTC](https://internals.rust-lang.org/t/bit-interleaving-in-std/23681/2 "2025-11-04T00:19:12Z")
> [@NyxCode](#): > > the x86 `pdep` instruction of the BMI extension, which can do everything in one pass. Being much more general, I'd expect it to perform worse than the other algorithms, though i have not benchmarked anything. (It's actually part of BMI2.) If you have any Intel CPU with BMI2 (about 2013 or later), or an AMD Zen 3 or later, `PDEP` seems to have 3-cycle latency and 1 per cycle throughput, and should beat the alternative methods shown in Bit Twiddling Hacks by a good margin. ([uops.info table](https://uops.info/table.html?search=pdep&cb_lat=on&cb_tp=on&cb_uops=on&cb_ports=on&cb_HSW=on&cb_ZEN3=on&cb_measurements=on&cb_doc=on&cb_bmi=on&checkbox=on)) ---
**Author:** ![scottmcm](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/scottmcm/32/2355_2.png) [@scottmcm](https://internals.rust-lang.org/u/scottmcm)\ **Post date:** [November 4, 2025, 12:27am UTC](https://internals.rust-lang.org/t/bit-interleaving-in-std/23681/4 "2025-11-04T00:27:22Z")
> [@NyxCode](#): > > as well as advice on what to do to actually get this into std. One thing that comes to mind is whether there are any codegen backends that have this as an intrinsic, because if the best way to use it in LLVM, say, if via an intrinsic, that's something that only core can do. But if not, it's not _obvious_ to me that this is common enough that it would need to be in core, vs in a crate that can be used by the things that need it. ---
**Author:** ![pitaj](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/pitaj/32/11262_2.png) [@pitaj](https://internals.rust-lang.org/u/pitaj)\ **Post date:** [November 4, 2025, 1:58am UTC](https://internals.rust-lang.org/t/bit-interleaving-in-std/23681/5 "2025-11-04T01:58:22Z")
Clang appears have BMI2 intrinsics for this [https://clang.llvm.org/doxygen/bmi2intrin\_8h\_source.html](https://clang.llvm.org/doxygen/bmi2intrin_8h_source.html) Looks like GCC does as well. These are Intel-defined intrinsics ---
**Author:** ![NyxCode](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/nyxcode/32/13374_2.png) [@NyxCode](https://internals.rust-lang.org/u/NyxCode)\ **Post date:** [November 4, 2025, 3:20am UTC](https://internals.rust-lang.org/t/bit-interleaving-in-std/23681/6 "2025-11-04T03:20:49Z")
I benchmarked interleaving two `u32` into one `u64` on a Ryzen 5950x. `pdep` is indeed faster, not only for the "spread bits by one" operation, but also for the full interleaving. That I assumed might be faster with the bit-fiddeling algorithm since the two "spread bits" operations get vectorized. ---
**Author:** ![NyxCode](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/nyxcode/32/13374_2.png) [@NyxCode](https://internals.rust-lang.org/u/NyxCode)\ **Post date:** [November 4, 2025, 3:48am UTC](https://internals.rust-lang.org/t/bit-interleaving-in-std/23681/7 "2025-11-04T03:48:41Z")
It seems like there's an [open proposal for C++](https://eisenwave.github.io/cpp-proposals/bit-permutations.html#intro-bit-expand) for a portable `pdep` in the form of `bit_expand`. The [proposed implementation](https://github.com/eisenwave/cxx26-bit-permutations/blob/a9f85f8cb0daef34db018ff5ffa3ceac65ce904d/bit_permutations.hpp#L890-L968) uses intrinsics (when available) on x86 and ARM, with a fallback implementation shifting every bit into the right place one-by-one. Having that operation available in a portable manner is exciting, although I am sceptical that the fallback implementation would have acceptable performance for a constant mask. I'd be surprised if LLVM managed to turn that into the five shift+or+and operations of the ["Interleave bits by Binary Magic Numbers"](https://graphics.stanford.edu/%7Eseander/bithacks.html#InterleaveBMN) algorithm. On the other hand, a `u32::spread_bits(n: u32)` or `u32::spread_bits()` might be easier to optimize when no specialized instruction is available. ---
**Author:** ![CodesInChaos](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/codesinchaos/32/5211_2.png) [@CodesInChaos](https://internals.rust-lang.org/u/CodesInChaos)\ **Post date:** [November 4, 2025, 5:55pm UTC](https://internals.rust-lang.org/t/bit-interleaving-in-std/23681/8 "2025-11-04T17:55:19Z")
> `u32::spread_bits(n: u32)` or `u32::spread_bits()` It should definitely be the former. The proper place to optimize such an expression is LLVM, which is already designed to detect runtime parameters being compile-time constants and to optimize based on that. ---
**Author:** ![NyxCode](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/nyxcode/32/13374_2.png) [@NyxCode](https://internals.rust-lang.org/u/NyxCode)\ **Post date:** [December 6, 2025, 10:45am UTC](https://internals.rust-lang.org/t/bit-interleaving-in-std/23681/9 "2025-12-06T10:45:35Z")
update: it seems like @okaneco & @quaternic [have put in the work to get a portable PDEP into std](https://github.com/rust-lang/rust/issues/149069). Very exciting!