# Bit twiddling hack

**URL:** <https://users.rust-lang.org/t/bit-twiddling-hack/95485>\
**Category:** uncategorized\
**Created:** [June 15, 2023, 10:33am UTC](https://users.rust-lang.org/t/bit-twiddling-hack/95485 "2023-06-15T10:33:15Z")\
**Posts on this page:** 13\
**Page:** 1

<div class="post-metadata">

**Author:** ![anon80458984](https://avatars.discourse-cdn.com/v4/letter/a/53a042/32.png) [@anon80458984](https://users.rust-lang.org/u/anon80458984)\
**Post date:** [June 15, 2023, 10:33am UTC](https://users.rust-lang.org/t/bit-twiddling-hack/95485/1 "2023-06-15T10:33:15Z")

</div>

Let x:u64 be viewed as a vector of length 64, where each elem is a bit 0 or 1.

Let k be the number of 1 bits in x.

Let the indices of the 1's be i\_0, i\_1, ... i\_{k-1}.

What is the fastest way, given (c, x) to compute i\_c ? Notation here a bit bad, as `i` is depend on `x`.

Basically I want to be able to rapidly compute: where does the 1st 1 appear? Where does the 2nd 1 appear? Where does the 3rd 1 appear? ...

---

<div class="post-metadata">

**Author:** ![SkiFire13](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/skifire13/32/17959_2.png) [@SkiFire13](https://users.rust-lang.org/u/SkiFire13)\
**Post date:** [June 15, 2023, 10:37am UTC](https://users.rust-lang.org/t/bit-twiddling-hack/95485/2 "2023-06-15T10:37:26Z")

</div>

For the first and last you could use `leading_zeros` and `trailing_zeros` and do some math to get the actual index. To calculate e.g. the second you could mask off the first 1, and then the second would become the first (which you can efficiently get the index of) and so on.

---

<div class="post-metadata">

**Author:** ![anon80458984](https://avatars.discourse-cdn.com/v4/letter/a/53a042/32.png) [@anon80458984](https://users.rust-lang.org/u/anon80458984)\
**Post date:** [June 15, 2023, 10:46am UTC](https://users.rust-lang.org/t/bit-twiddling-hack/95485/3 "2023-06-15T10:46:03Z")

</div>

Do you know how many ops this is? I'm looking for something similar to [Bit Twiddling Hacks](https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive) , but instead of counting bits, calculates the index.

---

<div class="post-metadata">

**Author:** ![alice](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/alice/32/9777_2.png) [@alice](https://users.rust-lang.org/u/alice)\
**Post date:** [June 15, 2023, 10:51am UTC](https://users.rust-lang.org/t/bit-twiddling-hack/95485/4 "2023-06-15T10:51:13Z")

</div>

Regarding the linked loop, that loop would work if you stop when reaching the count you want. The iteration counter of the loop is your index.

A solution using `leading_zeros` or `trailing_zeros` would let you skip several zeros in one iteration (and these are usually single assembly instructions, so they are cheap). Still the running time depends on which bit you want; the 10th bit takes 10 times as many ops as the first bit.

---

<div class="post-metadata">

**Author:** ![samuelpilz](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/samuelpilz/32/33384_2.png) [@samuelpilz](https://users.rust-lang.org/u/samuelpilz)\
**Post date:** [June 15, 2023, 10:55am UTC](https://users.rust-lang.org/t/bit-twiddling-hack/95485/5 "2023-06-15T10:55:46Z")

</div>

The linked "hack" might be suboptimal. The `count_ones` function is actually implemented by a single instruction on some architectures ([x86](https://www.felixcloutier.com/x86/popcnt)). Same with leading\_zeros and trailing\_zeros.

---

<div class="post-metadata">

**Author:** ![SkiFire13](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/skifire13/32/17959_2.png) [@SkiFire13](https://users.rust-lang.org/u/SkiFire13)\
**Post date:** [June 15, 2023, 11:03am UTC](https://users.rust-lang.org/t/bit-twiddling-hack/95485/6 "2023-06-15T11:03:44Z")

</div>

The operation of getting the index of the first bit set is just a single instruction (at least on x64), so that's quite fast. However this only works if there is a bit set (i.e. the number is not 0). If it's 0 then the result of the instruction is undefined, so those two methods need to check for that case too, which bloats the assembly a bit. This could however be optimized out if the optimizer sees it is an impossible case, but this depends on your code.

---

<div class="post-metadata">

**Author:** ![alice](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/alice/32/9777_2.png) [@alice](https://users.rust-lang.org/u/alice)\
**Post date:** [June 15, 2023, 11:06am UTC](https://users.rust-lang.org/t/bit-twiddling-hack/95485/7 "2023-06-15T11:06:14Z")

</div>

Using the `count_ones` method, it is possible to determine if a given answer is too small or large. This makes it possible to use binary search:

```rust
fn find_pos(x: u64, c: u32) -> u64 {
    let mut pos = 0;
    
    let mut pos_bit = 1 << 5;
    while pos_bit != 0 {
        let pos_with_bit = pos | pos_bit;
        let mask = (1 << (pos_with_bit - 1)) - 1;
        let count = (x & mask).count_ones();
        if count <= c {
            pos = pos_with_bit;
        }
        
        pos_bit = pos_bit >> 1;
    }
    pos - 1
}

```

The loop will iterate six times so you can unroll it, and the `if count <= c` can probably be made branchless.

---

<div class="post-metadata">

**Author:** ![user16251](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/user16251/32/30527_2.png) [@user16251](https://users.rust-lang.org/u/user16251)\
**Post date:** [June 16, 2023, 1:15pm UTC](https://users.rust-lang.org/t/bit-twiddling-hack/95485/8 "2023-06-16T13:15:22Z")

</div>

The `bsf` and `bsr` have bad behavior when the input is zero, but `tzcnt` and `lzcnt` return the width of the type in bits.

---

<div class="post-metadata">

**Author:** ![user16251](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/user16251/32/30527_2.png) [@user16251](https://users.rust-lang.org/u/user16251)\
**Post date:** [June 16, 2023, 1:19pm UTC](https://users.rust-lang.org/t/bit-twiddling-hack/95485/9 "2023-06-16T13:19:54Z")

</div>

Can you provide more context? For problems like this there is no one "fastest" solution. It really depends on how many problems you have to do at once and how the output is formatted. Are you willing to put a big table in L1? Can you use vector instructions? Is just using trailz in a loop fast enough for your application?

---

<div class="post-metadata">

**Author:** ![scottmcm](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/scottmcm/32/4286_2.png) [@scottmcm](https://users.rust-lang.org/u/scottmcm)\
**Post date:** [June 16, 2023, 9:31pm UTC](https://users.rust-lang.org/t/bit-twiddling-hack/95485/10 "2023-06-16T21:31:44Z")

</div>

> [@user16251](#):
>
> The `bsf` and `bsr` have bad behavior when the input is zero

Note that this is avoidable by working in `NonZeroU64` instead, as that tells LLVM it doesn't need to worry about those cases: [https://rust.godbolt.org/z/8Wbh9hdxr](https://rust.godbolt.org/z/8Wbh9hdxr)

---

<div class="post-metadata">

**Author:** ![khimru](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/khimru/32/31344_2.png) [@khimru](https://users.rust-lang.org/u/khimru)\
**Post date:** [June 17, 2023, 12:19am UTC](https://users.rust-lang.org/t/bit-twiddling-hack/95485/11 "2023-06-17T00:19:36Z")

</div>

> [@scottmcm](#):
>
> Note that this is avoidable by working in `NonZeroU64` instead, as that tells LLVM it doesn't need to worry about those cases: [https://rust.godbolt.org/z/8Wbh9hdxr](https://rust.godbolt.org/z/8Wbh9hdxr)

Alternatively you may decide that you don't want to worry about 10+ years old CPUs ([Haswell](https://en.wikipedia.org/wiki/Haswell_(microarchitecture)) or [Piledrier](https://en.wikipedia.org/wiki/Piledriver_(microarchitecture)) and everything after that support `lzcnt`/`tzcnt` and LLVM [knows how to use them](https://rust.godbolt.org/z/GjfheaccK)).

---

<div class="post-metadata">

**Author:** ![user16251](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/user16251/32/30527_2.png) [@user16251](https://users.rust-lang.org/u/user16251)\
**Post date:** [June 17, 2023, 1:50am UTC](https://users.rust-lang.org/t/bit-twiddling-hack/95485/12 "2023-06-17T01:50:17Z")

</div>

Rereading your original post you might want to use `pdep` and `pext`. If you deposit `1 << c` in the mask `x` it will go to the position of the `c`th set bit in `x` which you can then read with `tzcnt`. If you want to decode bit sets you may find Daniel Lemire's series of articles interesting; here's [one post](https://lemire.me/blog/2022/05/06/fast-bitset-decoding-using-intel-avx-512/). Of course you need a CPU with `pdep` or you can implement it by hand with the methods Hank Warren writes about in _Hacker's Delight_ (buy this book!).

---

<div class="post-metadata">

**Author:** ![system](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/system/32/51372_2.png) [@system](https://users.rust-lang.org/u/system)\
**Post date:** [September 15, 2023, 1:50am UTC](https://users.rust-lang.org/t/bit-twiddling-hack/95485/13 "2023-09-15T01:50:52Z")

</div>

Closed on September 15, 2023, 1:50am UTC

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.
