Decompose positive integer into 2^p+m

General Usage
,
1

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> 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:

"""
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?

2

maybe with ndigits instead?

function decompose(x)
    p = ndigits(x, base=2) - 1
    p, x - (1 << p)
end
3

Thanks, that’s the official API but it amounts to the same thing.

4

the remainder is just n&(n-1)

5

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

6

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, see my next answer:

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> Core.sizeof(big(1))
16
7

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.

8

sorry n should have been x

9

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.

10

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

11

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> @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…

12

It should be

p = 64 - leading_zeros(x) - 1
13

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