# Decompose positive integer into 2^p+m

**URL:** <https://discourse.julialang.org/t/decompose-positive-integer-into-2-p-m/138893>\
**Category:** General Usage\
**Tags:** question, bit-twiddling\
**Created:** [August 18, 2026, 1:41pm UTC](https://discourse.julialang.org/t/decompose-positive-integer-into-2-p-m/138893 "2026-08-18T13:41:17Z")\
**Posts on this page:** 13\
**Page:** 1

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [August 18, 2026, 1:41pm UTC](https://discourse.julialang.org/t/decompose-positive-integer-into-2-p-m/138893/1 "2026-08-18T13:41:17Z")

</div>

This is a bit-wrangling question: I would like to decompose a positive integer `x` into 2^p+m, for the highest p such that m \ge 0.

Expected output:

```julia
julia> for i in 1:7
       println(i => decompose(i))
       end
1 => (0, 0)
2 => (1, 0)
3 => (1, 1)
4 => (2, 0)
5 => (2, 1)
6 => (2, 2)
7 => (2, 3)

```

an example implementation, but it uses an internal function:

```julia
"""
Let `p` be the highest integer such that ``x = 2^p + m`` and `m ≥ 0`. Return `p, m`.
"""
function decompose(x::Integer)
    @assert x > 0
    p = Base.top_set_bit(x) - 1
    p, x - (1 << p)
end

```

Can I improve on this?

---

<div class="post-metadata">

**Author:** ![langestefan](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/langestefan/32/207923_2.png) [@langestefan](https://discourse.julialang.org/u/langestefan)\
**Post date:** [August 18, 2026, 1:55pm UTC](https://discourse.julialang.org/t/decompose-positive-integer-into-2-p-m/138893/2 "2026-08-18T13:55:20Z")

</div>

maybe with `ndigits` instead?

```julia-auto
function decompose(x)
    p = ndigits(x, base=2) - 1
    p, x - (1 << p)
end

```

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [August 18, 2026, 2:03pm UTC](https://discourse.julialang.org/t/decompose-positive-integer-into-2-p-m/138893/3 "2026-08-18T14:03:32Z")

</div>

> [@langestefan](#):
>
> maybe with `ndigits` instead?

Thanks, that’s the official API but it amounts to the [same thing](https://github.com/JuliaLang/julia/blob/76ffa8c2fcc2cb020e0c4624c8ac0218663e9a6e/base/intfuncs.jl#L771).

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [August 18, 2026, 2:09pm UTC](https://discourse.julialang.org/t/decompose-positive-integer-into-2-p-m/138893/4 "2026-08-18T14:09:51Z")

</div>

the remainder is just `n&(n-1)`

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [August 18, 2026, 2:19pm UTC](https://discourse.julialang.org/t/decompose-positive-integer-into-2-p-m/138893/5 "2026-08-18T14:19:27Z")

</div>

@Oscar_Smith: can you clarify a bit please? There is no `n` in my code.

---

<div class="post-metadata">

**Author:** ![Palli](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/palli/32/3380_2.png) [@Palli](https://discourse.julialang.org/u/Palli)\
**Post date:** [August 18, 2026, 2:23pm UTC](https://discourse.julialang.org/t/decompose-positive-integer-into-2-p-m/138893/6 "2026-08-18T14:23:15Z")

</div>

In what sense? This ~~doesn’t work~~ for BigInt (but does for Int128). I suppose you don’t care or need it.

EDIT: Not better, just as good (after sign fix, didn’t change speed I was measuring), see my next answer:

```julia-auto
julia> @btime decompose(UInt(1)) # same speed as for leading_zeros(1) which is basically just the one lzcnt instruction
  2.407 ns (0 allocations: 0 bytes)
(0, 0x0000000000000000)

vs 2.973 ns for your, with:

function decompose2(x::UInt64)
           # @assert x > 0
           # top_set_bit(x::BitInteger) = 8sizeof(x) - leading_zeros(x)
           p = 64 - leading_zeros(x) - 1
           p, x - (1 << p)
end

```

Base.top\_set\_bit is there to get access to `lzcnt` assembly instruction as I suppose you know (it does seem to be used for BigInt too, a bit surprisingly).

> help?\> Base.top\_set\_bit  
> │ Warning  
> │  
> │ The following bindings may be internal; they may change or be removed in future versions:  
> │  
> │ • Base.top\_set\_bit
> 
> top\_set\_bit(x::Integer)::Integer ..

That’s strictly not true, ~~since it only takes in Base.BitInteger~~. I suppose the docs could be changed to reflect that; or made more general to account for BigInt too. I’m guessing BitInteger doesn’t cover Int256 that might be in a package, so Integer intentional…

Note, I thought would not work for BigInt, since it uses sizeof (and it Core.sizeof), and would be nonsensical, but it seems taken care of:

```julia-auto
julia> Core.sizeof(big(1))
16

```

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [August 18, 2026, 2:25pm UTC](https://discourse.julialang.org/t/decompose-positive-integer-into-2-p-m/138893/7 "2026-08-18T14:25:11Z")

</div>

> [@Palli](#):
>
> BigInt (but does for Int128). I suppose you don’t care or need it.

Precisely, I only care about bits types. For the purposes of this exercise, one can assume `Int`.

Also, just to clarify: I have a solution already, I am just curious, I always learn a lot from solutions to these bit wrangling problems.

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [August 18, 2026, 2:30pm UTC](https://discourse.julialang.org/t/decompose-positive-integer-into-2-p-m/138893/8 "2026-08-18T14:30:08Z")

</div>

sorry n should have been x

---

<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:** [August 18, 2026, 2:32pm UTC](https://discourse.julialang.org/t/decompose-positive-integer-into-2-p-m/138893/9 "2026-08-18T14:32:31Z")

</div>

> [@Oscar\_Smith](#):
>
> n should have been x

I think `n` should be `2^p` for `n&(n-1)` to be the remainder.

EDIT: I wanted to say that `x&(n-1)` is the remainder.

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [August 18, 2026, 2:35pm UTC](https://discourse.julialang.org/t/decompose-positive-integer-into-2-p-m/138893/10 "2026-08-18T14:35:40Z")

</div>

@Oscar_Smith, @matthias314: neither of those suggestions work, eg `3&(3-1)==2`, and `(n = (1 << p); n&(n-1))` is just zero always.

---

<div class="post-metadata">

**Author:** ![Palli](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/palli/32/3380_2.png) [@Palli](https://discourse.julialang.org/u/Palli)\
**Post date:** [August 18, 2026, 2:36pm UTC](https://discourse.julialang.org/t/decompose-positive-integer-into-2-p-m/138893/11 "2026-08-18T14:36:18Z")

</div>

> [@Palli](#):
>
> `@btime decompose(UInt(1))`

Yours if fine, the min sometime beat mine when testing again but shouldn’t, and occasionally I get your exact min with mine too (my machine is a bit noisy, it seemed consistent when I first benchmarked), and if fully generic:

```julia-auto
julia> @benchmark decompose(1)
BenchmarkTools.Trial: 10000 samples with 1000 evaluations per sample.
 Range (min … max): 1.944 ns … 30.947 ns ┊ GC (min … max): 0.00% … 0.00%
 Time (median): 2.629 ns ┊ GC (median): 0.00%

```

Emulating the assembly instruction in software would be slower… and I can’t see your source code can be much simpler; my `@code_native decompose2(1)` is much shorter, I worried a bit about for your, but I guess the fast path there fast enough…

---

<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:** [August 18, 2026, 2:54pm UTC](https://discourse.julialang.org/t/decompose-positive-integer-into-2-p-m/138893/12 "2026-08-18T14:54:53Z")

</div>

> [@Palli](#):
>
> `p = 64 + leading_zeros(x) - 1`

It should be

```julia-auto
p = 64 - leading_zeros(x) - 1

```

---

<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:** [August 18, 2026, 3:02pm UTC](https://discourse.julialang.org/t/decompose-positive-integer-into-2-p-m/138893/13 "2026-08-18T15:02:50Z")

</div>

In the (unlikely) case that performance matters, one could replace `1 << p` by `1 << (p % UInt)`. This avoids testing whether `p` is negative.