How to efficiently enumerate bit vectors of length N such that no two adjacent bits are set simultaneously, using only bit operations (not recursion)? You can assume N <= 64.
By "efficient", we mean the complexity is (much) smaller than O(N * 2^N), because the naive way takes O(N * 2^N) (i.e. enumerating all of bit vectors and then removing those contradict the condition).
For example, when N = 4, I'd like to have
000010001010etc.
but not
1100(0th and 1st are both set)0110(1st and 2nd are both set)1111(all are set)etc.
This Japanese book says there is such a way, but not explains about it at all, so I'm just posting this question.
CodePudding user response：
As suggested in harold's comment, the sequence is known as Fibbinary numbers and OEIS A003714 shows an efficient implementation.
I implemented and compared the following three methods:
naive
recursion (suggested in MrSmith42's comment)
efficient algorithm (shown in OEIS)
Performance:
n = 32
loop: 9.726627375s
recursion: 26.339083ms
efficient: 14.795916ms
Rust code (Rust Playground):
//naive method
fn f1(n: usize) -> Vec<usize> {
let mut mem = Vec::with_capacity(1 << n);
'a: for i in 0..(1 << n) {
for j in 1..n {
if ((i & (1 << (j - 1)) != 0) && (i & (1 << j) != 0)) {
continue 'a;
}
}
mem.push(i);
}
mem
}
//recursive method
fn f2(cur: usize, i: usize, n: usize, mem: &mut Vec<usize>) {
if (i == n) {
mem.push(cur);
return;
}
if (i == 0) {
f2(cur, i 1, n, mem);
f2(cur | (1 << i), i 1, n, mem);
} else {
f2(cur, i 1, n, mem);
if (cur & (1 << (i - 1)) == 0) {
f2(cur | (1 << i), i 1, n, mem);
}
}
}
//efficient method
//The sequence is known as `Fibbinary numbers`.
//ref: |https://oeis.org/A003714|
fn f3(n: usize) -> Vec<usize> {
let mut mem = Vec::with_capacity(1 << n);
let mut x = 0;
loop {
mem.push(x);
let y = !(x >> 1);
x = (x - y) & y;
if ((1 << n) & x != 0) {
break;
}
}
mem
}
use std::time::Instant;
fn main() {
let n = 32;
let start = Instant::now();
let mut mem1 = f1(n);
println!("loop: {:?}", start.elapsed());
let start = Instant::now();
let mut mem2 = Vec::with_capacity(1 << n);
f2(0, 0, n, &mut mem2);
println!("recursion: {:?}", start.elapsed());
let start = Instant::now();
let mut mem3 = f3(n);
println!("efficient: {:?}", start.elapsed());
mem1.sort();
mem2.sort();
mem3.sort();
assert_eq!(mem1, mem2);
assert_eq!(mem1, mem3);
}
Side note:
Given an integer x, one can know if x is a Fibbinary number by (x << 1) & x == 0 (proof: trivial by the definition of Fibbinary numbers).
CodePudding user response：
Start with 1.
On each iteration, take all binary numbers of length k and append '0' and '01' to the end of each (separately), turning each into two new bitvectors of length k 1 and k 2.
Repeat until you have all bitvecs up to the length you want.
Ruby code:
def get_bitvecs(max_len)
ans = []
unprocessed_bitvecs = [[], ['1']]
parity = 1
loop do
cur_bv = unprocessed_bitvecs[parity].shift # take first element from array
cur_len = cur_bv.length
unprocessed_bitvecs[(parity 1) % 2].append(cur_bv '0')
unprocessed_bitvecs[parity].append(cur_bv '01')
ans.append(cur_bv)
if unprocessed_bitvecs[parity][0].length > cur_len
return ans if cur_len >= max_len
parity = (parity 1) % 2
end
end
end
Output of code:
> get_bitvecs(7)
=>
["1",
"10",
"101",
"100",
"1001",
"1010",
"1000",
"10101",
"10001",
"10010",
"10100",
"10000",
"100101",
"101001",
"100001",
"101010",
"100010",
"100100",
"101000",
"100000",
"1010101",
"1000101",
"1001001",
"1010001",
"1000001",
"1001010",
"1010010",
"1000010",
"1010100",
"1000100",
"1001000",
"1010000",
"1000000"]
CodePudding user response：
Assuming these bit vectors are generated consecutively as integers, they form the sequence oeis.org/A003714 as pointed out by harold in comments. A trivial way to generate this sequence is to simply iterate through the integers in ascending order and eliminate all that have two adjacent bits in their binary representation.
For this, we can modify the null-byte detecting technique invented by Alan Mycroft in 1987, modified to find bit-pairs (instead of bytes) that are zero. Two adjacent 1-bits form a bit pair with value 3, so we need to XOR with the integer in which all bit- pairs have value 3 prior to applying Mycroft's "magic". Mycroft's detection works on naturally aligned bit groups. To find bit pairs with value 3 starting at odd bit indexes, we need to also examine the original value shifted right by 1.
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
/*
Derived from Alan Mycroft's null-byte detection, posted to comp.lang.c on April 9, 1987.
Original at: https://groups.google.com/g/comp.lang.c/c/2HtQXvg7iKc/m/xOJeipH6KLMJ
*/
#define aligned_bitpair_zero(x) ((x - 0x55555555) & (~x & 0xaaaaaaaa))
int main (void)
{
for (uint32_t x = 0; x <= 264; x ) {
uint32_t s = x ^ 0xffffffff; // looking for bit-pairs with value 3
uint32_t sf = aligned_bitpair_zero (s); // examine bit-pairs at even bit indexes
uint32_t t = s >> 1;
uint32_t tf = aligned_bitpair_zero (t); // examine bit-pairs at odd bit indexes
if (!(sf || tf)) printf ("%u, ", x);
};
return EXIT_SUCCESS;
}
The output of the above program should be:
0, 1, 2, 4, 5, 8, 9, 10, 16, 17, 18, 20, 21, 32, 33, 34, 36, 37, 40, 41, 42, 64, 65, 66, 68, 69, 72, 73, 74, 80, 81, 82, 84, 85, 128, 129, 130, 132, 133, 136, 137, 138, 144, 145, 146, 148, 149, 160, 161, 162, 164, 165, 168, 169, 170, 256, 257, 258, 260, 261, 264,