# Shifting the bit in the array

**URL:** <https://discourse.julialang.org/t/shifting-the-bit-in-the-array/100586>\
**Category:** General Usage\
**Created:** [June 20, 2023, 3:14am UTC](https://discourse.julialang.org/t/shifting-the-bit-in-the-array/100586 "2023-06-20T03:14:56Z")\
**Posts on this page:** 10\
**Page:** 2

<div class="post-metadata">

**Author:** ![divon](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/divon/32/50659_2.png) [@divon](https://discourse.julialang.org/u/divon)\
**Post date:** [June 21, 2023, 5:20am UTC](https://discourse.julialang.org/t/shifting-the-bit-in-the-array/100586/22 "2023-06-21T05:20:29Z")

</div>

Hello everyone,  
I would like to propose this kind of method

```julia
g = 1
z[1, 1] = [0, 0, 0, 0] #since this array has no 1s, then we can move to next

g = 2
z[2, 1] = [0, 0, 0, 1] #this array is generated first
#for the next step, the bit is moved to the next position
z[2, 2] = [0, 0, 1, 0]
z[2, 3] = [0, 1, 0, 0]
z[2, 4] = [1, 0, 0, 0] #for g = 1, we stop when bit hit this position

g = 3
z[3, 1] = [0, 0, 1, 1] #same as before, this array is generated
#then move the first left side of bit 1s
z[3, 2] = [0, 1, 0, 1]
z[3, 3] = [1, 0, 0, 1]
#after the first moved bit is hit the last position, we move the other bit
z[3, 4] = [1, 0, 1, 0]
z[3, 5] = [1, 1, 0, 0] #and here is the stopping condition for g = 2

g = 4
z[4, 1] = [0, 1, 1, 1] #this array also generated in the first step
z[4, 2] = [1, 0, 1, 1] #then move most left of bit 1s
z[4, 3] = [1, 1, 0, 1]
z[4, 4] = [1, 1, 1, 0] #and here we stop for g = 3

g = 5
z[5, 1] = [1, 1, 1, 1] #here the bit is generated and after that, we check the position. since there is no moving space then we will stop.

```

If there is any advice about this problem, please feel free to post it here. 😁

---

<div class="post-metadata">

**Author:** ![barucden](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/barucden/32/26154_2.png) [@barucden](https://discourse.julialang.org/u/barucden)\
**Post date:** [June 21, 2023, 7:41am UTC](https://discourse.julialang.org/t/shifting-the-bit-in-the-array/100586/23 "2023-06-21T07:41:12Z")

</div>

Let me try to summarize.

# How to generate all binary vectors of length `n` that contain exactly `k` _one_s?

The answer, based on @Dan’s, is:

```julia
using Combinatorics
function _binary_vec(n, ix)
    v = zeros(Bool, n)
    v[ix] .= true
    return v
end

# Returns a generator of all binary vectors of length `n` with exactly `k` ones
binary_vectors(n, k) = (_binary_vec(n, ix) for ix in combinations(1:n, k))

```

I am using `collect` to see the generated values:

```julia-auto
julia> collect(binary_vectors(4, 0))
1-element Vector{Vector{Bool}}:
 [0, 0, 0, 0]

julia> collect(binary_vectors(4, 1))
4-element Vector{Vector{Bool}}:
 [1, 0, 0, 0]
 [0, 1, 0, 0]
 [0, 0, 1, 0]
 [0, 0, 0, 1]

julia> collect(binary_vectors(4, 2))
6-element Vector{Vector{Bool}}:
 [1, 1, 0, 0]
 [1, 0, 1, 0]
 [1, 0, 0, 1]
 [0, 1, 1, 0]
 [0, 1, 0, 1]
 [0, 0, 1, 1]

```

# How to generate all binary vectors of length `n` ordered by the number of ones?

You can use the `binary_vectors` function to generate vectors for values `k=1,...,n`:

```julia
# Generates all binary vectors of length `n` ordered by the number of ones
all_binary_vectors(n) = (v for k in 0:n for v in binary_vectors(n, k))

julia> collect(all_binary_vectors(4))
16-element Vector{Vector{Bool}}:
 [0, 0, 0, 0]
 [1, 0, 0, 0]
 [0, 1, 0, 0]
 [0, 0, 1, 0]
 [0, 0, 0, 1]
 [1, 1, 0, 0]
 [1, 0, 1, 0]
 [1, 0, 0, 1]
 [0, 1, 1, 0]
 [0, 1, 0, 1]
 [0, 0, 1, 1]
 [1, 1, 1, 0]
 [1, 1, 0, 1]
 [1, 0, 1, 1]
 [0, 1, 1, 1]
 [1, 1, 1, 1]

```

# Problems

- If you set `n` to a _very_ large number (like `n=2^32`), none of the individual vectors can be constructed. The length of any array is just constrained (by the memory in any case).
- If you set `n` to be large (like `n=50`), it is practically infeasible to iterate through the vectors because there are `2^n` such vectors.

Especially the second point is a problem of the naive algorithm, not the implementation. Your algorithm has the exponential complexity of `2^n`, so you cannot resolve it by a smarter implementation.

As @gdalle mentioned, one way would be to exploit the fact that the vectors with the same number of ones are equivalent in some sense. That way you don’t have to iterate through all of them and treat them as one class. This, of course, depends on your specific task and might not be suitable for you.

---

<div class="post-metadata">

**Author:** ![divon](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/divon/32/50659_2.png) [@divon](https://discourse.julialang.org/u/divon)\
**Post date:** [June 21, 2023, 9:03am UTC](https://discourse.julialang.org/t/shifting-the-bit-in-the-array/100586/24 "2023-06-21T09:03:45Z")

</div>

Thank you very much for your summary, @barucden. I will try to implement your suggestion in my simulation.

> [@divon](#):
>
> Hello everyone,  
> I would like to propose this kind of method
> 
> ```julia
> g = 1
> z[1, 1] = [0, 0, 0, 0] #since this array has no 1s, then we can move to next
> 
> g = 2
> z[2, 1] = [0, 0, 0, 1] #this array is generated first
> #for the next step, the bit is moved to the next position
> z[2, 2] = [0, 0, 1, 0]
> z[2, 3] = [0, 1, 0, 0]
> z[2, 4] = [1, 0, 0, 0] #for g = 1, we stop when bit hit this position
> 
> g = 3
> z[3, 1] = [0, 0, 1, 1] #same as before, this array is generated
> #then move the first left side of bit 1s
> z[3, 2] = [0, 1, 0, 1]
> z[3, 3] = [1, 0, 0, 1]
> #after the first moved bit is hit the last position, we move the other bit
> z[3, 4] = [1, 0, 1, 0]
> z[3, 5] = [1, 1, 0, 0] #and here is the stopping condition for g = 2
> 
> g = 4
> z[4, 1] = [0, 1, 1, 1] #this array also generated in the first step
> z[4, 2] = [1, 0, 1, 1] #then move most left of bit 1s
> z[4, 3] = [1, 1, 0, 1]
> z[4, 4] = [1, 1, 1, 0] #and here we stop for g = 3
> 
> g = 5
> z[5, 1] = [1, 1, 1, 1] #here the bit is generated and after that, we check the position. since there is no moving space then we will stop.
> 
> ```
> 
> If there is any advice about this problem, please feel free to post it here. 😁

Also, I have discussed this with my friend, and this method that I have proposed can’t be used. Because there are some sequence skipped by this method.

---

<div class="post-metadata">

**Author:** ![mkitti](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mkitti/32/12459_2.png) [@mkitti](https://discourse.julialang.org/u/mkitti)\
**Post date:** [June 21, 2023, 9:46am UTC](https://discourse.julialang.org/t/shifting-the-bit-in-the-array/100586/25 "2023-06-21T09:46:31Z")

</div>

```julia
julia> sort(0x1:0xf, by=x->sum(x .& (0x1,0x2,0x4,0x8) .!= 0)) .|> x->x .& (0x1,0x2,0x4,0x8) .!= 0
15-element Vector{NTuple{4, Bool}}:
 (1, 0, 0, 0)
 (0, 1, 0, 0)
 (0, 0, 1, 0)
 (0, 0, 0, 1)
 (1, 1, 0, 0)
 (1, 0, 1, 0)
 (0, 1, 1, 0)
 (1, 0, 0, 1)
 (0, 1, 0, 1)
 (0, 0, 1, 1)
 (1, 1, 1, 0)
 (1, 1, 0, 1)
 (1, 0, 1, 1)
 (0, 1, 1, 1)
 (1, 1, 1, 1)

```

More compact:

```julia
julia> f(x) = x .& (0x1,0x2,0x4,0x8) .!= 0
f (generic function with 1 method)

julia> sort(0x1:0xf, by=sum ∘ f) .|> f
15-element Vector{NTuple{4, Bool}}:
 (1, 0, 0, 0)
 (0, 1, 0, 0)
 (0, 0, 1, 0)
 (0, 0, 0, 1)
 (1, 1, 0, 0)
 (1, 0, 1, 0)
 (0, 1, 1, 0)
 (1, 0, 0, 1)
 (0, 1, 0, 1)
 (0, 0, 1, 1)
 (1, 1, 1, 0)
 (1, 1, 0, 1)
 (1, 0, 1, 1)
 (0, 1, 1, 1)
 (1, 1, 1, 1)

```

If want a slightly different order:

```julia
julia> sort(0x1:0xf, by=sum ∘ f) .|> reverse ∘ f
15-element Vector{NTuple{4, Bool}}:
 (0, 0, 0, 1)
 (0, 0, 1, 0)
 (0, 1, 0, 0)
 (1, 0, 0, 0)
 (0, 0, 1, 1)
 (0, 1, 0, 1)
 (0, 1, 1, 0)
 (1, 0, 0, 1)
 (1, 0, 1, 0)
 (1, 1, 0, 0)
 (0, 1, 1, 1)
 (1, 0, 1, 1)
 (1, 1, 0, 1)
 (1, 1, 1, 0)
 (1, 1, 1, 1)

```

Also there is the function `count_ones`.

```julia
julia> sort(0x0:0xf, by=count_ones) .|> x->reverse(digits(x, base=2, pad=4))
16-element Vector{Vector{Int64}}:
 [0, 0, 0, 0]
 [0, 0, 0, 1]
 [0, 0, 1, 0]
 [0, 1, 0, 0]
 [1, 0, 0, 0]
 [0, 0, 1, 1]
 [0, 1, 0, 1]
 [0, 1, 1, 0]
 [1, 0, 0, 1]
 [1, 0, 1, 0]
 [1, 1, 0, 0]
 [0, 1, 1, 1]
 [1, 0, 1, 1]
 [1, 1, 0, 1]
 [1, 1, 1, 0]
 [1, 1, 1, 1]

```

---

<div class="post-metadata">

**Author:** ![divon](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/divon/32/50659_2.png) [@divon](https://discourse.julialang.org/u/divon)\
**Post date:** [June 21, 2023, 11:44am UTC](https://discourse.julialang.org/t/shifting-the-bit-in-the-array/100586/26 "2023-06-21T11:44:50Z")

</div>

Thank you very much for your advice, @mkitti. I have tried to generate with `pad=1024` and it works great. I will try to implement it in my simulation.

---

<div class="post-metadata">

**Author:** ![moble](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/moble/32/23535_2.png) [@moble](https://discourse.julialang.org/u/moble)\
**Post date:** [June 21, 2023, 3:05pm UTC](https://discourse.julialang.org/t/shifting-the-bit-in-the-array/100586/27 "2023-06-21T15:05:53Z")

</div>

I’m still not sure I understand what you want to do, but if the arrays just represent the bits in an integer then this is easy:

> [@divon](#):
>
> I just want to arrange the array based on the number of 1s in it.

As several people have suggested, don’t bother creating the arrays, just create the integers and arrange the integers. The built-in function [`count_ones`](https://docs.julialang.org/en/v1/base/numbers/#Base.count_ones) gives you the number of 1s in the binary representation of the integer, and [`sort`](https://docs.julialang.org/en/v1/base/sort/#Base.sort) will sort them by that:

```julia
julia> sort(1:16, by=count_ones)
16-element Vector{Int64}:
  1
  2
  4
  8
 16
  3
  5
  6
  9
 10
 12
  7
 11
 13
 14
 15

```

To see what this looks like in binary, we can also use [`bitstring`](https://docs.julialang.org/en/v1/base/numbers/#Base.bitstring) to show the 1s and 0s (converting to `UInt8` just to make things easier to read):

```julia
julia> println.(bitstring.(UInt8.(sort(1:16, by=count_ones))));
00000001
00000010
00000100
00001000
00010000
00000011
00000101
00000110
00001001
00001010
00001100
00000111
00001011
00001101
00001110
00001111

```

A lot of the operations you’re talking about on these arrays of bits can be done directly on integers, because they’re very common operations. For example, `xor(3,5)` just works out of the box. They’re called [“bitwise operators”](https://docs.julialang.org/en/v1/manual/mathematical-operations/#Bitwise-Operators). It’s standard to use unsigned integers (`UInt` and friends) so you don’t have to worry about the sign bit. More generally, “bit twiddling” also works on integers. I wouldn’t be surprised if there are more, but there’s at least [one package just for some bit twiddling tricks](https://docs.juliahub.com/Twiddle/FGh1V/1.1.2/). There’s also [the classic page of “Bit Twiddling Hacks”](https://graphics.stanford.edu/~seander/bithacks.html) that any good nerd should know about.

One example that might be relevant for you is from [your other question](https://discourse.julialang.org/t/check-the-sum-of-a-certain-array-index/100552). I would translate

```julia
a = [0, 0, 0, 1, 0, 1, 0, 1]
b = [1, 2, 3, 5]

```

into the integer equivalents (ignoring a possible endianness ambiguity)

```julia
a = 21
b = 232 # Has 1s in binary representation at indices [1,2,3,5]

```

Then the sum over values in `a` at indices `b` translates simply to

```julia
count_ones(a & b)

```

(Bit twiddlers would call `b` the “mask”.)

---

<div class="post-metadata">

**Author:** ![divon](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/divon/32/50659_2.png) [@divon](https://discourse.julialang.org/u/divon)\
**Post date:** [June 22, 2023, 8:38pm UTC](https://discourse.julialang.org/t/shifting-the-bit-in-the-array/100586/28 "2023-06-22T20:38:39Z")

</div>

Thank you very much for the advice, @moble. I have implemented it in my simulation, but once again it returns an error when I try with a length of 1024. I think I need to read the paper that proposes this method deeper; maybe there are some hints in it.

---

<div class="post-metadata">

**Author:** ![moble](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/moble/32/23535_2.png) [@moble](https://discourse.julialang.org/u/moble)\
**Post date:** [June 22, 2023, 9:12pm UTC](https://discourse.julialang.org/t/shifting-the-bit-in-the-array/100586/29 "2023-06-22T21:12:19Z")

</div>

> [@divon](#):
>
> it returns an error when I try with a length of 1024

Again, I’m not really clear on what you mean. Do you mean that you want to represent things with up to 1024 bits? If so, you’ll need a specialized integer type. The largest [“native” integer](https://docs.julialang.org/en/v1/manual/integers-and-floating-point-numbers/#Integers-and-Floating-Point-Numbers) (in Julia, or any language) is `UInt128`, which has [drumroll] 128 bits. Fortunately, Julia also provides [the `BigInt` type](https://docs.julialang.org/en/v1/manual/integers-and-floating-point-numbers/#Arbitrary-Precision-Arithmetic), which will be slower than native types, but probably not so slow that you’ll need to worry about. And it will easily handle that many bits:

```julia
julia> c = BigInt(2)^1024
179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624224137216

julia> count_ones(c)
1

julia> count_ones(c-1)
1024

```

But note the size of that 2^{1024} \approx 1.7976931348623159\times 10^{308} (which is a little bigger than even the biggest `Float64`). If your plan is to iterate through (or sort) all those possibilities, it might take a little while…

---

<div class="post-metadata">

**Author:** ![divon](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/divon/32/50659_2.png) [@divon](https://discourse.julialang.org/u/divon)\
**Post date:** [June 22, 2023, 10:01pm UTC](https://discourse.julialang.org/t/shifting-the-bit-in-the-array/100586/30 "2023-06-22T22:01:16Z")

</div>

Just like you said, @moble. There is a possibility that I will calculate array a with all the generated arrays. There are so many hints in your previous reply, and I need to read and understand them one by one. Because right now, I just copied the code that you wrote without understanding each of your messages.

---

<div class="post-metadata">

**Author:** ![moble](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/moble/32/23535_2.png) [@moble](https://discourse.julialang.org/u/moble)\
**Post date:** [June 22, 2023, 10:17pm UTC](https://discourse.julialang.org/t/shifting-the-bit-in-the-array/100586/31 "2023-06-22T22:17:07Z")

</div>

> [@divon](#):
>
> There is a possibility that I will calculate array a with all the generated arrays.

Okay, but just to be clear, when I said “it might take a little while…” it was my attempt at dry humor. It’s totally unfeasible for 1024 bits: even with all the computing power in the world it would take far longer than the age of the universe. 16 bits should be easy enough; 32 bits is pushing the limits on current computers; 64 is surely beyond what is possible in the world today.

Though I don’t know what your underlying problem is, perhaps a statistical approach might suit you. That is, you might be able to select random subsets of all possible “arrays” of 1024 bits. For example, [`rand(0:BigInt(2)^1024, 100_000)`](https://docs.julialang.org/en/v1/stdlib/Random/#Base.rand) chooses 100,000 random integers between 0 and 2^{1024} (inclusive). This uses a “uniform” [distribution](https://en.wikipedia.org/wiki/Probability_distribution); you might have to think more carefully about the distribution that you actually want.

Otherwise, again depending on your underlying problem, your only realistic option might be to prove some property of your problem that relates it to a more feasible one.

[Previous page](https://discourse.julialang.org/t/shifting-the-bit-in-the-array/100586.md?page=1)