# Rotate lower n bits

**URL:** <https://discourse.julialang.org/t/rotate-lower-n-bits/119923>\
**Category:** Performance\
**Created:** [September 26, 2024, 3:01pm UTC](https://discourse.julialang.org/t/rotate-lower-n-bits/119923 "2024-09-26T15:01:46Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![Nichola](https://avatars.discourse-cdn.com/v4/letter/n/f0a364/32.png) [@Nichola](https://discourse.julialang.org/u/Nichola)\
**Post date:** [September 26, 2024, 3:01pm UTC](https://discourse.julialang.org/t/rotate-lower-n-bits/119923/1 "2024-09-26T15:01:46Z")

</div>

I would like to rotate the lower n bits of an integer x by r.  
Here is my current solution :

```julia
function rotate_lower(x::Int, n::Int, r::Int)
    mask = (1 << n) - 1
    lower_bits = x & mask
    rotated_bits = (lower_bits >> r) | (lower_bits << (n - r))
    rotated_bits &= mask
    return (x & ~mask) | rotated_bits
end

```

Is there a more efficient way to go ? is it possible to do that faster ?

---

<div class="post-metadata">

**Author:** ![lbilli](https://avatars.discourse-cdn.com/v4/letter/l/59ef9b/32.png) [@lbilli](https://discourse.julialang.org/u/lbilli)\
**Post date:** [September 26, 2024, 3:15pm UTC](https://discourse.julialang.org/t/rotate-lower-n-bits/119923/2 "2024-09-26T15:15:38Z")

</div>

You might want to look into [`bitrotate()`](https://docs.julialang.org/en/v1/base/math/#Base.bitrotate).

---

<div class="post-metadata">

**Author:** ![foobar\_lv2](https://avatars.discourse-cdn.com/v4/letter/f/ee59a6/32.png) [@foobar\_lv2](https://discourse.julialang.org/u/foobar_lv2)\
**Post date:** [September 26, 2024, 11:12pm UTC](https://discourse.julialang.org/t/rotate-lower-n-bits/119923/3 "2024-09-26T23:12:41Z")

</div>

> [@Nichola](#):
>
> `lower_bits >> r`

You want `lower_bits >>> r` for correctness if `n=64` (logical right shift, not arithmetic right shift).

You should specify / think about desired behavior for “nonsensically large” `n` and `k` values. There is a long sorry story about [shift left `shl` producing poison values](https://llvm.org/docs/LangRef.html#shl-instruction) for stuff like `1<<65`, due to a mix of old x86 and C-language idiosyncracies, which leads to slow code on x86 (the specific julia semantics for 1\<\<65 are a bad match for both x86 and C, and hence llvm).

---

<div class="post-metadata">

**Author:** ![nsajko](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nsajko/32/221187_2.png) [@nsajko](https://discourse.julialang.org/u/nsajko)\
**Post date:** [September 27, 2024, 12:19am UTC](https://discourse.julialang.org/t/rotate-lower-n-bits/119923/4 "2024-09-27T00:19:58Z")

</div>

> [@foobar\_lv2](#):
>
> You should specify / think about desired behavior for “nonsensically large” `n` and `k` values.

💯

> [@foobar\_lv2](#):
>
> due to a mix of old x86 and C-language idiosyncracies

AFAIK RISC-V uses the same semantics, so I’m guessing this may not be just an “old x86 idiosyncrasy”. C is not relevant here, except as a comparison.

> [@foobar\_lv2](#):
>
> the specific julia semantics for 1\<\<65 are a bad match for both x86 and C, and hence llvm

Again, this doesn’t make sense. LLVM uses the same semantics as C, and this is completely OK, both for Julia and in general. It’s just that performance requires some care.

---

<div class="post-metadata">

**Author:** ![matthias314](https://avatars.discourse-cdn.com/v4/letter/m/a88e4f/32.png) [@matthias314](https://discourse.julialang.org/u/matthias314)\
**Post date:** [September 27, 2024, 1:25am UTC](https://discourse.julialang.org/t/rotate-lower-n-bits/119923/5 "2024-09-27T01:25:47Z")

</div>

> [@Nichola](#):
>
> is it possible to do that faster ?

If you have `0 <= r <= n < 64`, the following is faster:

```julia
function rotate_lower2(x::Int, n::Int, r::Int)
    n &= 63
    r &= 63
    s = (n-r) & 63
    mask = (1 << n) - 1
    lower_bits = x & mask
    rotated_bits = (lower_bits >>> r) | (lower_bits << s)
    rotated_bits &= mask
    return (x & ~mask) | rotated_bits
end

```

```julia
julia> x, n, r = rand(Int), 37, 12;
julia> @b rotate_lower($x, $n, $r)
4.750 ns

julia> @b rotate_lower2($x, $n, $r)
2.639 ns

```

This works because the bit shift operators check for “nonsensically large” and negative values. If the shifts are known to be between `0` and `63`, then the test is omitted in the final code.

---

<div class="post-metadata">

**Author:** ![foobar\_lv2](https://avatars.discourse-cdn.com/v4/letter/f/ee59a6/32.png) [@foobar\_lv2](https://discourse.julialang.org/u/foobar_lv2)\
**Post date:** [September 27, 2024, 8:02am UTC](https://discourse.julialang.org/t/rotate-lower-n-bits/119923/6 "2024-09-27T08:02:52Z")

</div>

> [@nsajko](#):
>
> LLVM uses the same semantics as C, and this is completely OK

One possible semantics of `x << n` for large `n` that make sense is “implementation defined”, i.e. “whatever the hardware can do best”. Due to C being C, it is instead “undefined” which translates to llvm “poison”.

In other words, it would be valid to compile

```julia-auto
void foo(){
   int x = (( (uint64_t) 1) << 65 ) ? 0 : 1);
   return;
}

```

into `void foo(){abort();}`.

This is bullshit and not acceptable for julia.

It might have been acceptable for julia to have sensible but hardware-dependent semantics of `<<` for large `n`. A standard precedent is propagation of NaN payloads in floating point ops – this is not quite defined and hardware dependent, but it is not poison either.

> [@nsajko](#):
>
> AFAIK RISC-V uses the same semantics

AFAIK aarch64 also uses the same semantics, presumably in order to go with the mainstream. Of course armv7 et al do `x << (n & 0xff)`, so we’re still hosed.

---

<div class="post-metadata">

**Author:** ![nsajko](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nsajko/32/221187_2.png) [@nsajko](https://discourse.julialang.org/u/nsajko)\
**Post date:** [September 27, 2024, 8:46am UTC](https://discourse.julialang.org/t/rotate-lower-n-bits/119923/7 "2024-09-27T08:46:26Z")

</div>

> [@foobar\_lv2](#):
>
> One possible semantics of `x << n` for large `n` that make sense is “implementation defined”, i.e. “whatever the hardware can do best”. Due to C being C, it is instead “undefined” which translates to llvm “poison”.

IMO “implementation defined behavior” isn’t any better than “undefined behavior”.

I think Julia made the only good choice for a modern high-level language. Especially because the performance is easy, in principle, to regain using something like an unreachable instruction. Although such a feature isn’t yet available to users at a high-level in Julia (except like in my package UnsafeAssume.jl, which has its drawbacks), I hope it’ll be available one day.