# How do I find the number of bits a number needs for storage

**URL:** <https://discourse.julialang.org/t/how-do-i-find-the-number-of-bits-a-number-needs-for-storage/93334>\
**Category:** General Usage\
**Tags:** data, bit-twiddling\
**Created:** [January 21, 2023, 8:18pm UTC](https://discourse.julialang.org/t/how-do-i-find-the-number-of-bits-a-number-needs-for-storage/93334 "2023-01-21T20:18:22Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![feanor12](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/feanor12/32/8212_2.png) [@feanor12](https://discourse.julialang.org/u/feanor12)\
**Post date:** [January 21, 2023, 8:18pm UTC](https://discourse.julialang.org/t/how-do-i-find-the-number-of-bits-a-number-needs-for-storage/93334/1 "2023-01-21T20:18:22Z")

</div>

I was looking into compression algorithms and storage schemes (like Simple-8b and xor-based compression ) and one thing they do is determine the highest set bit for a given number.

I wrote some code, but I feel this can be done better or in a more efficient way.

```julia
function find_highest_bit(n::Number)
  ui8_number = reinterpret(UInt8,[n])
  totalshift = 0
  for (i,byte) in enumerate(ui8_number)
    shift = 0
    while( (byte >> shift) > 0)
      shift = shift+1
    end
    if shift != 0 
      totalshift = shift+((i-1)*8) 
    end
  end
  return totalshift
end

```

> **This can then be used like this**
>
> ```julia
> # generate some sorted data
> julia> a = cumsum(rand(UInt8,10)).+100000000000;
> 10-element Vector{UInt64}:
> 0x000000174876e83b
> 0x000000174876e8c5
> 0x000000174876e97e
> 0x000000174876e9ab
> 0x000000174876ea68
> 0x000000174876eb2a
> 0x000000174876eb4c
> 0x000000174876ec28
> 0x000000174876ec4b
> 0x000000174876ed45
> 
> # calculate bits needed to store each number
> julia> sum(find_highest_bit.(a))
> 10-element Vector{Int64}:
> 37
> 37
> 37
> 37
> 37
> 37
> 37
> 37
> 37
> 37
> 
> # calculate bits when only the difference is stored
> julia> sum(find_highest_bit.(diff(a)))
> 9-element Vector{Int64}:
> 8
> 8
> 6
> 8
> 8
> 6
> 8
> 6
> 8
> 
> #same for float
> julia> a = 2000.0 .+ rand(10)
> 10-element Vector{Float64}:
> 2000.4285571858823
> 2000.6576141052876
> 2000.8451949182838
> 2000.810710858975
> 2000.2450630027245
> 2000.4849832339958
> 2000.7565738749688
> 2000.3952829518228
> 2000.6558837662135
> 2000.2400002168467
> 
> julia> find_highest_bit.(a)
> 10-element Vector{Int64}:
> 63
> 63
> 63
> 63
> 63
> 63
> 63
> 63
> 63
> 63
> 
> # some ugly xor of neighbors
> t = vcat(reinterpret.(eltype(a),[xor.(reinterpret(UInt8,a[i:i]),reinterpret(UInt8,a[i+1:i+1])) for i in 1:length(a)-1])...)
> 
> # this also needs less bits
> julia> find_highest_bit.(t)
> 9-element Vector{Int64}:
> 42
> 41
> 39
> 42
> 41
> 42
> 42
> 42
> 42
> 
> ```

Any hints are welcome.  
Thank you,

---

<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:** [January 21, 2023, 8:31pm UTC](https://discourse.julialang.org/t/how-do-i-find-the-number-of-bits-a-number-needs-for-storage/93334/2 "2023-01-21T20:31:00Z")

</div>

see [Add internal `top_set_bit` function by LilithHafner · Pull Request #47523 · JuliaLang/julia · GitHub](https://github.com/JuliaLang/julia/pull/47523)

---

<div class="post-metadata">

**Author:** ![feanor12](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/feanor12/32/8212_2.png) [@feanor12](https://discourse.julialang.org/u/feanor12)\
**Post date:** [January 21, 2023, 8:40pm UTC](https://discourse.julialang.org/t/how-do-i-find-the-number-of-bits-a-number-needs-for-storage/93334/3 "2023-01-21T20:40:04Z")

</div>

I guess this will be available in julia 1.10. 🙂

---

<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:** [January 21, 2023, 8:40pm UTC](https://discourse.julialang.org/t/how-do-i-find-the-number-of-bits-a-number-needs-for-storage/93334/4 "2023-01-21T20:40:54Z")

</div>

yeah but it’s implementation is usable now.

---

<div class="post-metadata">

**Author:** ![Dan](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dan/32/42581_2.png) [@Dan](https://discourse.julialang.org/u/Dan)\
**Post date:** [January 21, 2023, 10:33pm UTC](https://discourse.julialang.org/t/how-do-i-find-the-number-of-bits-a-number-needs-for-storage/93334/5 "2023-01-21T22:33:29Z")

</div>

Even without dedicated pull-request. Doesn’t:

```julia
64 - leading_zero(x)

```

do the trick (for UInt64s)?

---

<div class="post-metadata">

**Author:** ![feanor12](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/feanor12/32/8212_2.png) [@feanor12](https://discourse.julialang.org/u/feanor12)\
**Post date:** [January 21, 2023, 11:40pm UTC](https://discourse.julialang.org/t/how-do-i-find-the-number-of-bits-a-number-needs-for-storage/93334/6 "2023-01-21T23:40:41Z")

</div>

Yes, `leading_zero` and `trailing_zeros` should be enough I think, but I did not find them.  
I only knew that there are some builtin calls for GCC like `__builtin_clz`