Is there an efficient way to construct b10101010101010101010101010101010?

Question

I want to construct the unsigned integer (4 bytes) represented by the binary string 10101010101010101010101010101010 (that's 16 1s and 16 0s).

Is there an efficient way to construct this value using bit manipulation? I could do it in a for loop, but I feel that's inefficient.

Any language works for me. I personally know c and C++.

Uh, isn't it 0xAAAAAAAA? Just make a string of length 4 whose chars are `0xAA`... — user541686, Jun 08 '13 at 18:43
@DavidFaux `1010` in binary is decimal 10 (it's easy to remember, for this exact same reason). And decimal 10 is `A` in hexadecimal. — , Jun 08 '13 at 18:44
@Mehrdad: Because he lives so close to the hexadecimal numbers that they are all his close friends. — Pieter Geerkens, Jun 08 '13 at 18:44
@DavidFaux: it is really obvious. 0xaa // 0x55 used to be used to perform RAM tests, etc. The first/last two bytes of the boot sector used to be aa55, too, IIRC. — wildplasser, Jun 08 '13 at 18:45
By the way, if you want to [have binary literals in C, that's possible too.](http://stackoverflow.com/questions/15114140/writing-binary-number-system-in-c-code/15114188#15114188) — , Jun 08 '13 at 18:49
Many languages support bit syntax. Why dont you tell us what you are using? — leppie, Jun 08 '13 at 18:57

score 5 · Accepted Answer · answered Jun 08 '13 at 18:45

5

Just read bits 4 by 4 and treat them as hex:

your number is just 0xAAAAAAAA.

answered Jun 08 '13 at 18:45

Emilio Garavaglia

20,229
2
46
63

aka.nice · Answer 2 · 2013-06-09T20:39:19.953

1

With a fixed number of bits, this is a bit obvious...

But for a variable number of bits, such pattern can be obtained by integer division as demonstrated here http://smallissimo.blogspot.fr/2011/07/revisiting-sieve-of-erathostenes.html

EDIT More detailed explanations below:

The idea is that :

2r01 * 2r11 -> 2r11
2r0101 * 2r11 -> 2r1111
2r010101 * 2r11 -> 2r111111

So inversely, we can apply an exact division:

2r111111 / 2r11 -> 2r010101

If we want 2r101010 rather than 2r010101, just add 1 more bit (but the division is then inexact, I assume quotient is given by // like in Smalltalk) :

2r1111111 // 2r11 -> 2r101010

2r1111111 can be constructed easily, it is a power of 2 minus 1, 2^7-1, which can also be obtained by a bith shift (1<<7)-1.

In your case, your constant is ((1<<33)-1)//3, or if you write it in C/C++ ((1ULL<<33)-1)/3
(In Smalltalk we don't care of integer length, they are of arbitrary length, but in most language we must make sure the operands fits on a native integer length).

Note that division also work for bit patterns of longer length like 2r100100100, divide by 2r111, and for a bit pattern of length p, divide by 2^p-1 that is (1<<p)-1

edited Jun 09 '13 at 20:39

answered Jun 09 '13 at 16:19

aka.nice

9,100
1
28
40

That was not a question. – Ramon Snir Jun 09 '13 at 17:13
@RamonSnir The question is how to construct, so this might be an answer, though I agree, the answer is useless if the pattern is of fixed length – aka.nice Jun 09 '13 at 19:37
At least summarize the formula `(2^64-1)*2/3` (the article is long and mostly irrelevant). But the question was about fixed size. I will not that this "trick" doesn't work for all powers of two, only the even ones. – Ramon Snir Jun 09 '13 at 19:52
@RamonSnir yes it was a lazy answer, because too much for calculating a constant! But the article is relevant, the essence of the algorithm is precisely this property of bit division and it is right at the beginning of the article. I edited now to make sure there is no mis-understanding, the algorithm should work for any bit length. – aka.nice Jun 09 '13 at 20:47

Is there an efficient way to construct b10101010101010101010101010101010?

2 Answers2