Menu
What I want to do is take a 64-bit unsigned integer consisting of pairs of bits and create from it a 32-bit integer containing 0 if both bits in the corresponding pair are 0 and 1 otherwise. In other words, convert something that looks like :
01 00 10 11 into something that looks like this
1 0 1 1 The two obvious solutions are either the brute force loop or a lookup table for each byte and then do eight lookups and combine them into a final result with OR and bit shifting but I'm sure there should be an efficient means of bit-twiddling this. I will be doing this for a 64-bit integers in C++ but if anyone knows of efficient ways to do this for shorter integers I'm sure I can figure out how to scale it up.
522
A 64-bit register can hold any of 264 (over 18 quintillion or 1.8×1019) different values. The range of integer values that can be stored in 64 bits depends on the integer representation used.
You can declare 8-, 16-, 32-, or 64-bit integer variables by using the __intN type specifier, where N is 8, 16, 32, or 64. The types __int8 , __int16 , and __int32 are synonyms for the ANSI types that have the same size, and are useful for writing portable code that behaves identically across multiple platforms.
There is no standard way for having data type greater than 64 bits. You should check the documentation of your systems, some of them define 128 bits integers. However, to really have flexible size integers, you should use an other representation, using an array for instance.
In particular, an actual implementation has to be careful of overflowing 64 bit integers. The simple and portable solution he proposes is to break each of a and b into 2 32-bit numbers and then multiply those 32 bit numbers using the 64 bit multiply operation. If we write:
The simple and portable solution he proposes is to break each of a and b into 2 32-bit numbers and then multiply those 32 bit numbers using the 64 bit multiply operation. If we write: provided the calculation is performed using 128 bit (or greater) arithmetic.
This gives 4 32 bit multiplies plus some shifts. Do them in 64 bits, and do the carries manually, and you'll get the high portion. Note that an approximation of the high portion can be done with fewer multiplies -- accurate within 2^33 or so with 1 multiply, and within 1 with 3 multiplies.
If you're using gcc and the version you have supports 128 bit numbers (try using __uint128_t) then performing the 128 multiply and extracting the upper 64 bits is likely to be the most efficient way of getting the result. If your compiler doesn't support 128 bit numbers, then Yakk's answer is correct.
Here is a portable C++ implementation. It seems to work during my brief testing. The deinterleave code is based on this SO question.
uint64_t calc(uint64_t n) { // (odd | even) uint64_t x = (n & 0x5555555555555555ull) | ((n & 0xAAAAAAAAAAAAAAAAull) >> 1); // deinterleave x = (x | (x >> 1)) & 0x3333333333333333ull; x = (x | (x >> 2)) & 0x0F0F0F0F0F0F0F0Full; x = (x | (x >> 4)) & 0x00FF00FF00FF00FFull; x = (x | (x >> 8)) & 0x0000FFFF0000FFFFull; x = (x | (x >> 16)) & 0x00000000FFFFFFFFull; return x; } gcc, clang, and msvc all compile this down to about 30 instructions.
From the comments, there is a modification that can be made.
The possibly (?) improved code is:
uint64_t calc(uint64_t n) { // (odd | even) uint64_t x = (n | (n >> 1)) & 0x5555555555555555ull; // single bits // ... the restdeinterleave x = (x | (x >> 1)) & 0x3333333333333333ull; // bit pairs x = (x | (x >> 2)) & 0x0F0F0F0F0F0F0F0Full; // nibbles x = (x | (x >> 4)) & 0x00FF00FF00FF00FFull; // octets x = (x | (x >> 8)) & 0x0000FFFF0000FFFFull; // halfwords x = (x | (x >> 16)) & 0x00000000FFFFFFFFull; // words return x; } If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
