A puzzle for 2013

DEFINE
Year = New
Happy = Variable, Objective = True
END DEFINE

OK so here's a hypothetical problem for you thinkers....

Using any make of PLC, (or a PC program if that's your thing), and any programming language you choose, what is the shortest method (in terms of number of instructions) of non-destructively reversing the bit order in an 8-bit byte?

No prizes, but I'd be interested to see what you guys might come up with.

The simplest way is obviously 8 rungs of code that maps bit 0 to 7, 1 to 6 etc., but I'd be particularly impressed with a solution that didn't use any "intermediate" storage, which IS possible, but it involves some lateral thinking.

Not an original puzzle-problem, I came across it many years ago in a computing magazine. Some of the solutions given I didn't understand at the time..... maybe I won't this time around either...

The "lateral thinking" solution I mentioned above was certainly the outright winner in terms of code efficiency, but it was ruled out on the basis that it wasn't strictly handled in code, but the author received a special commendation for his thinking !

Converting from big endian to little endian is encountered commonly enough in modern computing that Intel assembly language includes an instruction for doing just what you describe.

bswap

I don't think it can get shorter than that.

TConnolly said:

Converting from big endian to little endian is encountered commonly enough in modern computing that Intel assembly language includes an instruction for doing just what you describe.

bswap

I don't think it can get shorter than that.

Click to expand...

Doesn't that swap the "byte" order and not the "bit" order?

I believe its a bit swap (not to be confused with C language bswap) - it would of necessity need to be a bit swap to be useful for changing from big to little endian, but its been a very long time since I did anything in Intel assembly, so if someone demonstrates otherwise I stand corrected.


I have a list of bit hacks that show about half a dozen ways to do this. This is maybe the simplest hack, but you need a 64 bit processor.

b = (b * 0x0202020202ULL & 0x010884422010ULL) % 1023;

Hello,

You want the rotate instruction, ROR and use the carry flag.

My2c.

BIT swap was what I wanted....

Bit 7 = Bit 0
Bit 6 = Bit 1
Bit 5 = Bit 2
Bit 4 = Bit 3
Bit 3 = Bit 4
Bit 2 = Bit 5
Bit 1 = Bit 6
Bit 0 = Bit 7

As you can see, intermediate storage is necessary for the simpler methods, as bit 7 is overwritten by bit 0 etc.

I'm already intrigued as to how the b = (b * 0x0202020202ULL & 0x010884422010ULL) % 1023 actually works !! (can you explain the "ULL" reference and what it means?)

TConnolly said:

it would of necessity need to be a bit swap to be useful for changing from big to little endian,

Click to expand...

I have only ever seen the terms Big and Little Endian used in reference to Byte order and not Bit Order. This being a result of the original arbitrary choice of how to order the bytes of a 16 bit integer.

255 - Value = Inversed Value

A couple more:
This one requires a few more operations than the one I posted before but doesn't need a 64 bit processor, 32 bit will do.

b = ((b * 0x0802LU & 0x22110LU) | (b * 0x8020LU & 0x88440LU)) * 0x10101LU >> 16;



This one lets us pick the bits we want to swap, for example we could swap bits 4-11 instead of bits 0-7

unsigned int i, j; // positions of bit sequences to swap
unsigned int n; // number of consecutive bits in each sequence
unsigned int b; // bits to swap reside in b unsigned int r; //bit-swapped result goes here
unsigned int x = ((b >> i) ^ (b >> j)) & ((1U << n) - 1); // XOR temporary r = b ^ ((x << i) | (x << j));


One of the fastest executing would be to use a 256 entry look up table, but creating the table takes time.



edit to add: ULL is Unsigned Long Long (64bit) and forces the compiler to make the constant in that data type.


Most of these come from a book that I have on bit hacks, they are not my original creations.

Incidentally, the guy who did the best, but didn't win, used (1 or 2) PIO chip(s), and wired 7 out to 0 in, 6 out to 1 in, etc., then executed...

OUT BYTE, PIO
IN BYTE, PIO

...can't remember the exact syntax, but you get the drift.

I remember thinking at the time that the puzzle did not prohibit the use of I/O devices, so I thought he should have won, anyway the puzzle is posed looking for a software only solution....

TConnolly said:

One of the fastest executing would be to use a 256 entry look up table, but creating the table takes time.

Click to expand...

Probably the way I would do it....

TConnolly said:

A couple more:
This one requires a few more operations than the one I posted before but doesn't need a 64 bit processor, 32 bit will do.

b = ((b * 0x0802LU & 0x22110LU) | (b * 0x8020LU & 0x88440LU)) * 0x10101LU >> 16;



This one lets us pick the bits we want to swap, for example we could swap bits 4-11 instead of bits 0-7

unsigned int i, j; // positions of bit sequences to swap
unsigned int n; // number of consecutive bits in each sequence
unsigned int b; // bits to swap reside in b unsigned int r; //bit-swapped result goes here
unsigned int x = ((b >> i) ^ (b >> j)) & ((1U << n) - 1); // XOR temporary r = b ^ ((x << i) | (x << j));


One of the fastest executing would be to use a 256 entry look up table, but creating the table takes time.



edit to add: ULL is Unsigned Long Long (64bit) and forces the compiler to make the constant in that data type.


Most of these come from a book that I have on bit hacks, they are not my original creations.

Click to expand...

Are your "<<" and ">>" "shift lefts" and "shift rights" ?

Yes, >> and << are how you do shifts in C (these are shifts, not rotates, end bits are lost). Equivalent to multiplying or dividing 2ⁿ where n is number of bits to be shifted.

Here is another fun one:

Move the value in N7:0 to N7:1 and move the value in N7:1 to N7:0 without using any intermediate register.

example
Before
N7:0 = 105
N7:1 = 93

After
N7:0 = 93
N7:1 = 105

TConnolly said:

Here is another fun one:

Move the value in N7:0 to N7:1 and move the value in N7:1 to N7:0 without using any intermediate register.

example
Before
N7:0 = 105
N7:1 = 93

After
N7:0 = 93
N7:1 = 105

Click to expand...

Don't believe this is true - amplify where this does this, what PLC/SLC ??