# Faster way to find all bit arrays of weight n

**URL:** <https://discourse.julialang.org/t/faster-way-to-find-all-bit-arrays-of-weight-n/113658>\
**Category:** Performance\
**Created:** [April 30, 2024, 3:31pm UTC](https://discourse.julialang.org/t/faster-way-to-find-all-bit-arrays-of-weight-n/113658 "2024-04-30T15:31:31Z")\
**Posts on this page:** 15\
**Page:** 1

<div class="post-metadata">

**Author:** ![AwesomeQuest](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/awesomequest/32/38910_2.png) [@AwesomeQuest](https://discourse.julialang.org/u/AwesomeQuest)\
**Post date:** [April 30, 2024, 3:31pm UTC](https://discourse.julialang.org/t/faster-way-to-find-all-bit-arrays-of-weight-n/113658/1 "2024-04-30T15:31:31Z")

</div>

The obvious way to generate these bit arrays is something like:

```julia
function findbcn2s(b,n)
    bitstrs = digits.(2^n-1:2^b-1, base=2, pad=b) .|> BitVector
    filter(x->sum(x)==n, bitstrs)
end

```

I feel like this is horribly inefficient and there must be a faster way, but my combinatorics-fu isn´t good enough to figure it out.

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [April 30, 2024, 3:41pm UTC](https://discourse.julialang.org/t/faster-way-to-find-all-bit-arrays-of-weight-n/113658/2 "2024-04-30T15:41:17Z")

</div>

> [@AwesomeQuest](#):
>
> `bitstrs = digits.(2^n-1:2^b-1, base=2, pad=b) .|> BitVector`

If your `n` and `b` are small enough to fit into an `Int` (or `UInt` or similar), then why form a `BitVector` at all? Much more efficient to just query the bits of the integer directly.

---

<div class="post-metadata">

**Author:** ![AwesomeQuest](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/awesomequest/32/38910_2.png) [@AwesomeQuest](https://discourse.julialang.org/u/AwesomeQuest)\
**Post date:** [April 30, 2024, 3:59pm UTC](https://discourse.julialang.org/t/faster-way-to-find-all-bit-arrays-of-weight-n/113658/3 "2024-04-30T15:59:12Z")

</div>

Do you mean by using Bits.jl?  
So something like:

```julia
function findbcn2sv2(b,n)
    filter(x->sum(x)==n, bits.(2^n-1:2^b-1)) |> x->map(z->z[1:b], x)
end

```

This is significantly faster, thank you.

---

<div class="post-metadata">

**Author:** ![mbauman](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mbauman/32/31082_2.png) [@mbauman](https://discourse.julialang.org/u/mbauman)\
**Post date:** [April 30, 2024, 4:03pm UTC](https://discourse.julialang.org/t/faster-way-to-find-all-bit-arrays-of-weight-n/113658/4 "2024-04-30T16:03:28Z")

</div>

Sure, that’d be one way. You can also [`count_ones`](https://docs.julialang.org/en/v1/base/numbers/#Base.count_ones) directly

---

<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:** [April 30, 2024, 4:09pm UTC](https://discourse.julialang.org/t/faster-way-to-find-all-bit-arrays-of-weight-n/113658/5 "2024-04-30T16:09:34Z")

</div>

The other major improvement is that rather than generating all `2^b-1` and filtering, it is possible to generate them 1 at a time. (see [Combinatorics.jl/src/permutations.jl at master · JuliaMath/Combinatorics.jl · GitHub](https://github.com/JuliaMath/Combinatorics.jl/blob/master/src/permutations.jl) for how to do this in the general case, you can do it better in the case of bitarrays)

---

<div class="post-metadata">

**Author:** ![rocco\_sprmnt21](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rocco_sprmnt21/32/20127_2.png) [@rocco\_sprmnt21](https://discourse.julialang.org/u/rocco_sprmnt21)\
**Post date:** [April 30, 2024, 7:51pm UTC](https://discourse.julialang.org/t/faster-way-to-find-all-bit-arrays-of-weight-n/113658/6 "2024-04-30T19:51:54Z")

</div>

```julia

vv=[trues(6) for _ in 1:binomial(6,4)]

foreach(((i,idx),)->vv[i][idx].=false, enumerate(combinations(1:6,2)))

setindex!.(vv, Ref(repeat([false],2)),combinations(1:6,2))

```

```julia
digits.(findall(==(4),count_ones.(1:2^6)),base=2,pad=6)

```

```julia

function d2b(d)
    b=falses(6)
    i=6
    while d>=1
        #d,r=divrem(d,2)
        b[i]=d&1
        d>>=1
        i-=1
    end
    b
end

julia> @btime d2b.(findall(==(4),count_ones.(1:2^6)))
  735.135 ns (35 allocations: 2.41 KiB)
15-element Vector{BitVector}:
 [0, 0, 1, 1, 1, 1]
 [0, 1, 0, 1, 1, 1]
 [0, 1, 1, 0, 1, 1]
 [0, 1, 1, 1, 0, 1]
 [0, 1, 1, 1, 1, 0]
 [1, 0, 0, 1, 1, 1]
 [1, 0, 1, 0, 1, 1]
 [1, 0, 1, 1, 0, 1]
 [1, 0, 1, 1, 1, 0]
 [1, 1, 0, 0, 1, 1]
 [1, 1, 0, 1, 0, 1]
 [1, 1, 0, 1, 1, 0]
 [1, 1, 1, 0, 0, 1]
 [1, 1, 1, 0, 1, 0]
 [1, 1, 1, 1, 0, 0]

```

---

<div class="post-metadata">

**Author:** ![StefanKarpinski](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stefankarpinski/32/24_2.png) [@StefanKarpinski](https://discourse.julialang.org/u/StefanKarpinski)\
**Post date:** [April 30, 2024, 8:05pm UTC](https://discourse.julialang.org/t/faster-way-to-find-all-bit-arrays-of-weight-n/113658/7 "2024-04-30T20:05:14Z")

</div>

There’s also this thread on computing the next integer value with the same number of ones set: [Computing the preimage of count\_ones](https://discourse.julialang.org/t/computing-the-preimage-of-count-ones/104838).

---

<div class="post-metadata">

**Author:** ![greatpet](https://avatars.discourse-cdn.com/v4/letter/g/e495f1/32.png) [@greatpet](https://discourse.julialang.org/u/greatpet)\
**Post date:** [April 30, 2024, 8:52pm UTC](https://discourse.julialang.org/t/faster-way-to-find-all-bit-arrays-of-weight-n/113658/8 "2024-04-30T20:52:29Z")

</div>

> [@mbauman](#):
>
> You can also [`count_ones`](https://docs.julialang.org/en/v1/base/numbers/#Base.count_ones) directly

Does it use the [`popcount`](https://vaibhavsagar.com/blog/2019/09/08/popcount/) CPU instruction which is exactly for counting the number of nonzero bits?

---

<div class="post-metadata">

**Author:** ![mbauman](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mbauman/32/31082_2.png) [@mbauman](https://discourse.julialang.org/u/mbauman)\
**Post date:** [April 30, 2024, 8:59pm UTC](https://discourse.julialang.org/t/faster-way-to-find-all-bit-arrays-of-weight-n/113658/9 "2024-04-30T20:59:51Z")

</div>

It should, yep. You can check yourself with a `@code_native count_ones(123)`.

---

<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:** [April 30, 2024, 10:41pm UTC](https://discourse.julialang.org/t/faster-way-to-find-all-bit-arrays-of-weight-n/113658/10 "2024-04-30T22:41:55Z")

</div>

There is a package `SmallCollections` which is very useful for this, for example, to get UInts for 3-bit subsets of 6-bits:

```julia
julia> using SmallCollections

julia> map(x->x.mask, Subsets(6,3))
20-element Vector{UInt64}:
 0x0000000000000038
 0x0000000000000034
 0x0000000000000032
 0x0000000000000031
 0x000000000000002c
 0x000000000000002a
 0x0000000000000029
 0x0000000000000026
 0x0000000000000025
 0x0000000000000023
 0x000000000000001c
 0x000000000000001a
 0x0000000000000019
 0x0000000000000016
 0x0000000000000015
 0x0000000000000013
 0x000000000000000e
 0x000000000000000d
 0x000000000000000b
 0x0000000000000007

```

But keeping the subsets in their package representation is probably better:

```julia
julia> Subsets(4,2) |> collect
6-element Vector{SmallBitSet{UInt64}}:
 SmallBitSet([3,4])
 SmallBitSet([2,4])
 SmallBitSet([1,4])
 SmallBitSet([2,3])
 SmallBitSet([1,3])
 SmallBitSet([1,2])

```

Thanks to careful implementation by matthias314, this should be faster than alternatives. Link: SmallCollections.jl .

---

<div class="post-metadata">

**Author:** ![StefanKarpinski](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stefankarpinski/32/24_2.png) [@StefanKarpinski](https://discourse.julialang.org/u/StefanKarpinski)\
**Post date:** [May 1, 2024, 2:42am UTC](https://discourse.julialang.org/t/faster-way-to-find-all-bit-arrays-of-weight-n/113658/11 "2024-05-01T02:42:39Z")

</div>

Oh, that’s a really cool package—very Julian!

---

<div class="post-metadata">

**Author:** ![sgaure](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sgaure/32/14779_2.png) [@sgaure](https://discourse.julialang.org/u/sgaure)\
**Post date:** [May 1, 2024, 8:17am UTC](https://discourse.julialang.org/t/faster-way-to-find-all-bit-arrays-of-weight-n/113658/12 "2024-05-01T08:17:00Z")

</div>

I made this iterator some time ago for this purpose:

```julia
struct BitCombinations{T, T1, T2}
    weight::T1
    width::T2
    thelast::T
    function BitCombinations(weight, width, ::Type{T}) where {T}
        isbitstype(T) || throw(ArgumentError("$T is not a bitstype"))
        T1 = typeof(weight)
        T2 = typeof(width)
        new{T,T1,T2}(weight, width, ((-1 % T) >>> (8*sizeof(T) - weight)) << (width-weight))
    end
end
Base.length(fw::BitCombinations) = binomial(fw.width, fw.weight)
Base.IteratorEltype(::Type{<:BitCombinations}) = Base.HasEltype()
Base.eltype(::Type{<:BitCombinations{T}}) where T = T

# from https://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation
@inline function next_combination(x::T) where T
    t = x | (x-one(T))
    return (t+one(T)) | (((~t & -~t) - one(T)) >>> (trailing_zeros(x) + one(T)))
end

@inline function Base.iterate(fw::BitCombinations{T}) where T
    val = (-1 % T) >>> (8*sizeof(T) - fw.weight)
    return (val,val)
end

@inline function Base.iterate(fw::BitCombinations, state)
    state == fw.thelast && return nothing
    val = next_combination(state)
    return (val,val)
end

"""
bitcombinations(weight, width, ::Type{T}=UInt64)

Generate all bit patterns with `weight` bits set in a bit field of width `width`.
An iterator which returns integers of type `T` is created. The type `T` must be a bits type.
The patterns are returned in lexicographical order, that is, in arithmetic order.

Such combinations can also be generated by [`combinations`](@ref), but in case the
actual bit patterns are needed, this function is faster and non-allocating.

"""
function bitcombinations(weight::Integer, width::Integer, ::Type{T}=UInt64) where {T<:Integer}
    nbits = 8*sizeof(T)
    (0 ≤ weight ≤ width ≤ nbits) || 
        throw(ArgumentError(lazy"0 ≤ weight($weight) ≤ width($width) ≤ 8*sizeof($T)($nbits) failed"))
    BitCombinations(weight, width, T)
end

```

Usage:

```julia
julia> collect(bitcombinations(3,6,UInt8))
20-element Vector{UInt8}:
 0x07
 0x0b
 0x0d
 0x0e
 0x13
 0x15
 0x16
 0x19
 0x1a
 0x1c
 0x23
 0x25
 0x26
 0x29
 0x2a
 0x2c
 0x31
 0x32
 0x34
 0x38

```

Using such bitmasks e.g. for indexing into arrays is somewhat involved, but not very difficult, and can be made quite efficient. Like this function summing the elements of an array which are marked in a bitmask:

```julia
@inline blsr(x) = x & (x-true) # clear lowest set bit, compiles to single blsr instruction

function summask(P::Vector, bitmask)
    p = zero(eltype(P))
    while !iszero(bitmask)
        tz = trailing_zeros(bitmask)
        bitmask = blsr(bitmask)
        p += @inbounds P[tz+1]
    end
    return p
end

```

---

<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:** [May 1, 2024, 11:34pm UTC](https://discourse.julialang.org/t/faster-way-to-find-all-bit-arrays-of-weight-n/113658/13 "2024-05-01T23:34:15Z")

</div>

@sgaure’s code is faster than what I had so far in SmallCollections.jl. I’ve added improved `iterate` methods for `SmallBitSet` and `Subsets` to master; they will be included in the next release. Then @Dan’s solution based on my package will be as fast as the one using `bitcombinations`.

---

<div class="post-metadata">

**Author:** ![sgaure](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sgaure/32/14779_2.png) [@sgaure](https://discourse.julialang.org/u/sgaure)\
**Post date:** [May 2, 2024, 4:34pm UTC](https://discourse.julialang.org/t/faster-way-to-find-all-bit-arrays-of-weight-n/113658/14 "2024-05-02T16:34:51Z")

</div>

Came to think of it. I also made another thing to use with such indices. It works like

```julia
v = rand(10)
sum(v[BitIndices(0b01101)])

```

I.e. a vector indexed by a `BitIndices` creates an iterator over the marked indices. So one can create non allocating loops like,

```julia
for subset in flatten(bitcombinations(w, K) for w in 4:K)
    a += sum(v[BitIndices(subset)])
end

```

And `BitIndices` is an iterator as well `collect(BitIndices(0b01101)) == [1,3,4])`.

I’m not sure it’s error free with various generic inputs, but it works for my purposes. For all I know there’s something like this in `SmallCollections`, I haven’t had the time to look into it.

```julia
struct BitIndices{T,IT} <: AbstractIteratorIndices
    bits::T
    firstindex::IT
    BitIndices(v::T) where T = new{T,typeof(firstindex(v))}(v, firstindex(v)) 
    BitIndices(v::T, fi::IT) where {T,IT} = new{T,IT}(v,fi)
end
BitIndices(a::BitIndices) = a
Base.IteratorEltype(::Type{<:BitIndices}) = Base.HasEltype()
Base.eltype(::Type{<:BitIndices}) = Int
Base.length(ii::BitIndices) = count_ones(ii.bits)

function Base.iterate(bi::BitIndices, state=bi.bits)
    iszero(state) && return nothing
    trailing_zeros(state)+bi.firstindex, state & (state - true)
end
for op in (:&, :|, :⊻)
    @eval Base.$op(a::BitIndices, b::BitIndices) = BitIndices($op(promote(a.bits,b.bits)...))
end
Base.:(~)(a::BitIndices) = BitIndices(~a.bits)

struct IndexIterator{VT, IT}
    v::VT
    idx::IT
end

Base.length(ii::IndexIterator) = length(ii.idx)
Base.IteratorEltype(::Type{T}) where {VT, T<:IndexIterator{VT}} = Base.IteratorEltype(VT)
Base.eltype(::Type{<:IndexIterator{VT}}) where {VT} = eltype(VT)

Base.@propagate_inbounds @inline function Base.iterate(
    ii::IndexIterator, state=iterate(ii.idx)
    ) 
    isnothing(state) && return nothing
    next, istate = state
    return ii.v[next], iterate(ii.idx, istate)
end

Base.getindex(v::AbstractVector, idx::AbstractIteratorIndices) = IndexIterator(v, idx)

```

---

<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:** [May 2, 2024, 11:46pm UTC](https://discourse.julialang.org/t/faster-way-to-find-all-bit-arrays-of-weight-n/113658/15 "2024-05-02T23:46:04Z")

</div>

I’ve taken the function

```julia
function f(v, K)
    a = 0.0
    for subset in Iterators.flatten(bitcombinations(w, K) for w in 4:K)
        a += sum(v[BitIndices(subset)])
    end
    a
end

```

Note that I had to use `Iterators.flatten` and to add the line

```julia
abstract type AbstractIteratorIndices end

```

at the very beginning.

With SmallCollections.jl one would write

```julia
function ff(v, K)
    a = 0.0
    for subset in Iterators.flatten(Subsets(K, w) for w in 4:K)
        a += sum(@inbounds(v[i]) for i in subset)
    end
    a
end

```

Then for `K = 10` and `v = rand(K)` the SmallCollections code is about 20% faster than `BitIndices` on my machine. Without `@inbounds`, it’s about 15% slower. (I tried to add `@inbounds` to `BitIndices`, but it didn’t change anything. Also, I’m using the master version of SmallCollections, which has improved iterators taken from @sgaure’s code.)