Shifting the bit in the array

General Usage
22

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

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

23

Let me try to summarize.

How to generate all binary vectors of length n that contain exactly k ones?

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

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

# 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.

3 Likes
24

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

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.

25 
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> 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> 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> 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]
2 Likes
26

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.

27

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:

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 gives you the number of 1s in the binary representation of the integer, and sort will sort them by that:

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 to show the 1s and 0s (converting to UInt8 just to make things easier to read):

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”. 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. There’s also the classic page of “Bit Twiddling Hacks” that any good nerd should know about.

One example that might be relevant for you is from your other question. I would translate

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

into the integer equivalents (ignoring a possible endianness ambiguity)

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

count_ones(a & b)

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

8 Likes
28

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.

29

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 (in Julia, or any language) is UInt128, which has [drumroll] 128 bits. Fortunately, Julia also provides the BigInt type, 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> 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…

1 Like
30

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.

31

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) chooses 100,000 random integers between 0 and 2^{1024} (inclusive). This uses a “uniform” 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.

1 Like