Bit swizzling

"Rick C. Hodgin" <>
Sat, 5 Sep 2020 12:05:07 -0400

          From comp.compilers

Related articles
Bit swizzling (Rick C. Hodgin) (2020-09-05)
Re: Bit swizzling (Hans-Peter Diettrich) (2020-09-05)
Re: Bit Swizzling (John Levine) (2020-09-05)
Re: Bit swizzling (Kaz Kylheku) (2020-09-05)
Re: Bit swizzling ( (2020-09-06)
Re: Bit Swizzling (Chris) (2020-09-06)
Re: Bit swizzling (Martin Ward) (2020-09-07)
[5 later articles]
| List of all articles for this month |

From: "Rick C. Hodgin" <>
Newsgroups: comp.compilers
Date: Sat, 5 Sep 2020 12:05:07 -0400
Organization: Liberty Software Foundation
Injection-Info:; posting-host=""; logging-data="67025"; mail-complaints-to=""
Keywords: optimize, question
Posted-Date: 05 Sep 2020 12:45:39 EDT
Content-Language: en-US

Are there any algorithms which take a known-at-compile-time sequence
of bitwise operations on an 8-bit to 64-bit quantity, and optimize
them down to their minimal set of operations?

For example, if I have an 8-bit byte and I want to swizzle the bits

          Input: 07 06 05 04 03 02 01 00
        Output: 05 04 07 02 01 03 00 06

I can easily swizzle the data using a brute force method:

          v = get_value();
          o = 0;
          swizzle1(o, v, 0, 6);
          swizzle1(o, v, 1, 0);
          swizzle1(o, v, 2, 3);
          swizzle1(o, v, 3, 1);
          swizzle1(o, v, 4, 2);
          swizzle1(o, v, 5, 7);
          swizzle1(o, v, 6, 4);
          swizzle1(o, v, 7, 5);

          // Untested, off the top of my head
          void swizzle(unsigned char& o, unsigned char v, int s, int d)
                  o |= (((v & (1 << s)) >> s) << d);

And, of course, that algorithm can be optimized based on relative
values of s and d, and if s is 0, etc.

However, there also exists a minimal set of steps to complete that
swizzling because in the operation above, bits 5 and 4 are used in
sequence. It could be done using a swizzle2() operation, for example
and handle 2 bits at a time.

In addition, given the bit operator abilities that exist on various
CPUs there are potentially other combinations that exist behind an
operation, such as bitswap, where the order of bits flips or mirrors
across the center position.

Are there any existing algorithms which examine the operations that
must be conducted and then create an optimized / minimal sequence of
mechanical steps to conduct it given a constrained set of features
(such as those present on a given CPU)?

Thank you in advance.

Rick C. Hodgin

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.