How to de-interleave bits (UnMortonizing?)

by

Given that you know that every other bit is 0 in your application, you can do it like this:

x = (x | (x >> 1)) & 0x33333333;
x = (x | (x >> 2)) & 0x0f0f0f0f;
x = (x | (x >> 4)) & 0x00ff00ff;
x = (x | (x >> 8)) & 0x0000ffff;

The first step looks like this:

  0a0b0c0d0e0f0g0h0i0j0k0l0m0n0o0p   x
| 00a0b0c0d0e0f0g0h0i0j0k0l0m0n0o0   x >> 1
  --------------------------------
= 0aabbccddeeffgghhiijjkkllmmnnoop   x | (x >> 1)
& 00110011001100110011001100110011   0x33333333
  --------------------------------
= 00ab00cd00ef00gh00ij00kl00mn00op   (x | (x >> 1)) & 0x33333333

Then the second step works with two bits at a time, and so on.

More Related Contents:

  1. Implement division with bit-wise operator
  2. How to compute a 3D Morton number (interleave the bits of 3 ints)
  3. The difference between logical shift right, arithmetic shift right, and rotate right
  4. Fastest way to set __m256 value to all ONE bits
  5. Have you ever had to use bit shifting in real projects? [closed]
  6. Invalid solution for code challenge with operator restrictions
  7. Position of least significant bit that is set
  8. Are the shift operators () arithmetic or logical in C?
  9. How does XOR variable swapping work?
  10. Is shifting bits faster than multiplying and dividing in Java? .NET? [closed]
  11. C/C++ check if one bit is set in, i.e. int variable
  12. Checking if a bit is set or not
  13. Bitfield manipulation in C
  14. Fastest way to clamp a real (fixed/floating point) value?
  15. Efficiently find binary strings with low Hamming distance in large set
  16. Understanding PHP & (ampersand, bitwise and) operator
  17. What’s the fastest way to divide an integer by 3?
  18. Bitwise XOR of hexadecimal numbers
  19. Find out number of bits needed to represent a positive integer in binary?
  20. set the m-bit to n-bit [closed]
  21. Weird result of Java Integer left shift
  22. Count the number of set bits in a 32-bit integer
  23. What is “two’s complement”?
  24. Efficient bitwise operations for counting bits or find the right|left most ones
  25. What’s the quickest way to compute log2 of an integer in C#?
  26. Check if a number is non zero using bitwise operators in C
  27. Branchless code that maps zero, negative, and positive to 0, 1, 2
  28. Java storing two ints in a long
  29. Is there a way to perform a circular bit shift in C#?
  30. How can I test whether a number is a power of 2?

Leave a Comment