Go Down

Topic: LSB Vs MSB (Read 5774 times) previous topic - next topic


Hello All,

I've recovered a S-35390A I2C RTC chip on an old lexmark printer which I plan to use in a HL1606 LED Strip based MOOD LAMP I'm designing for a Xmas present.

The rev 1.2_00 Datasheet I have shows that this chip uses both MSB (for command) and LSB (for data).
Rev 4.0 is all LSB based as they've barely inverted the order of the command bits from the previous release.

After searching around and finding different options (including table based search) I've created the following code to invert the bits in a byte
using, in this case,  two global variables ABCD and its inverted DCBA:

Code: [Select]
void grab(int ABCD){
    for (int i=0 ; i < 8; i++){
      bitWrite(DCBA, 7 - i, bitRead(c,i));

It actually works fine but for my own Arduino code learning I'd like to know if this code is any good performance wise.

Thanks in advance for your feedback!



Oops, I did not update the code properly, it should read

Code: [Select]
void grab(int ABCD){
    for (int i=0 ; i < 8; i++){
      bitWrite(DCBA, 7 - i, bitRead(ABCD,i));

Stupid me  :smiley-slim:


Looks well expressed (with the fix).

You might find further inspiration about related bit hacks here: http://graphics.stanford.edu/~seander/bithacks.html#BitReverseObvious



Thanks billroy,

Great reading although most look like big overkill in my case!



A look-up table would be the most time efficient and lease space efficient solution.


This is what I would do:

Code: [Select]

//reverse a byte
unsigned char bitrev8_1(unsigned char bits) {
unsigned char tmp=0;

//bit reversing, msb to lsb
tmp |= (bits & 0x80)?0x01:0;
tmp |= (bits & 0x40)?0x02:0;
tmp |= (bits & 0x20)?0x04:0;
tmp |= (bits & 0x10)?0x08:0;
tmp |= (bits & 0x08)?0x10:0;
tmp |= (bits & 0x04)?0x20:0;
tmp |= (bits & 0x02)?0x40:0;
tmp |= (bits & 0x01)?0x80:0;
return tmp;

//reverse a byte
unsigned char bitrev8_2(unsigned char bits) {
//unsigned char tmp=0;

bits = ((bits >> 1) & 0x55) | ((bits << 1) & 0xaa);
bits = ((bits >> 2) & 0x33) | ((bits << 2) & 0xcc);
bits = (bits >> 4) | (bits << 4) ;
return bits;

//for compatibility - pick your version of bit reversal routines
#define bitrev8(dat) bitrev8_2(dat)

//bit reversal for 16 bit types
#define bitrev16(dat) (((unsigned short) bitrev8(dat) << 8) | ((unsigned short) bitrev8(dat >> 8)))

//bit reversal for 32 bit types
#define bitrev32(dat) (((unsigned long) bitrev16(dat) << 16) | ((unsigned long) bitrev16(dat >> 16)))

In your case, something like this would reverse a 16-bit type:

Code: [Select]

  ABCD = bitrev16(ABCD); //reverse a 16-bit type variable and store it back to itself

No global variables at all.

By changing the definition of bitrev(), you can pick / chose which 8-bit bit reversal routines you wish to use.


It's not obvious from your description whether you need to reverse the bits in the high byte or the low byte. The low byte is what you're actually reversing.

You code does not seem to transfer the content of the high byte at all. Wouldn't it be cleaner to copy the high byte across as-is (assuming you don't want it transformed)?

The reference to global variables is confusing (and sounds fugly). You're actually using an argument to pass in the input value, and returning the result via a global variable. That's not what your description implied. Why not simply return the transformed value and get away from the global variables completely?


Nov 28, 2012, 01:53 am Last Edit: Nov 28, 2012, 01:58 am by guix Reason: 1
I think this method is the fastest but I haven't measured..
Code: [Select]

uint8_t InvertBitOrder( uint8_t value )
 return ( (value * 0x0802UL & 0x22110UL) | (value * 0x8020UL & 0x88440UL) ) * 0x10101UL >> 16;


If I've worked it out correctly if can be done on 2 assembly instructions on a Mega, 4 on an Uno
[ I will NOT respond to personal messages, I WILL delete them, use the forum please ]


Hard to tell. Your approach uses unsigned long multification so it is likely faster on a 32-bit platform than on a 8-bit platform. Look-up table usually is the fastest but least efficient as well.

Some numbers:

On a 1MIPS avr, 1000 reversals took this much time, when compiled in release mode:

bitrev8_1: 60.2ms
bitrev8_2: 38.0ms
bitrev8_3: 35.8ms
bitrev8_4: 66.0ms
bitrev8_5: 245ms (your approach)

Those numbers certainly will change as you move to different chips / compiler / optimization levels.


Code: [Select]
void grab(int ABCD){
   for (int i=0 ; i < 8; i++){
     bitWrite(DCBA, 7 - i, bitRead(ABCD,i));

It's not great, but it will work.
The algorithms that use multiply are nice if your CPU has a fast multiply instruction (for longs), but the AVR doesn't.
There's a trivial algorithm (left shift from source to carry flag, right shift from carry flag to destination) that will do 8 bits in 16 instructions (and 16 cycles), in assembler.  (not counting the overhead of moving things into correct registers.)
2 assembly instructions on a Mega, 4 on an Uno

Really?  That doesn't seem likely.

This is a Frequently Discussed Topic in technical circles.  There's some good discussion (for AVR) here: http://www.avrfreaks.net/index.php?name=PNphpBB2&file=viewtopic&t=41613


Okay, sorry then :D


You need to wire 16 pins up to do the actual bit reversing, then on the Uno it might be:

Code: [Select]

byte rev (byte in)
  PORTD = in ;
  return  PINB | (PINC<<2) ;

D0 to A5
D1 to A4
D2 to A3
D3 to A2
D4 to A1
D5 to A0
D6 to D9
D7 to D8...
[ Other pins pulled down with resistors so they read low. ]

On the Mega there are lots of uncommited ports to play with where all 8 bits are pins, so just a single port write and single port read needed.


Actually there is another way to do it I think - the UART has an SPI mode, and if you couple that to the hardware SPI port and have one send MSB first and the other LSB first you can probably reverse two bytes simultaneously (well I'm guessing a bit).

This has the advantage of needing fewer pins wired up!
[ I will NOT respond to personal messages, I WILL delete them, use the forum please ]


Nov 28, 2012, 04:07 am Last Edit: Nov 28, 2012, 05:23 am by stimmer Reason: 1
Actually you only need four inductors  :P

Try this sketch on a Uno - just with three inductors (wired D2-D7,D3-D6,D4-D5) as it uses serial. I am using inductors around 10uH.

Code: [Select]

void setup() {

void loop() {
 static byte c=0;
 byte b=PIND;
 Serial.print(" Output:");
 byte d=0;
 b>>=2;for(int i=0;i<6;i++){d<<=1;d|=b&1;b>>=1;}
 Serial.print(" Check:");
 if((c>>2)==d)Serial.println(" Correct!");
 else Serial.println(" Wrong!");


And for non-believers....
Code: [Select]

Input:0 Output:0 Check:0 Correct!
Input:1 Output:100000 Check:1 Correct!
Input:10 Output:10000 Check:10 Correct!
Input:11 Output:110000 Check:11 Correct!
Input:100 Output:1000 Check:100 Correct!
Input:101 Output:101000 Check:101 Correct!
Input:110 Output:11000 Check:110 Correct!
Input:111 Output:111000 Check:111 Correct!
Input:1000 Output:100 Check:1000 Correct!
Input:1001 Output:100100 Check:1001 Correct!
Input:1010 Output:10100 Check:1010 Correct!
Input:1011 Output:110100 Check:1011 Correct!
Input:1100 Output:1100 Check:1100 Correct!
Input:1101 Output:101100 Check:1101 Correct!
Input:1110 Output:11100 Check:1110 Correct!
Input:1111 Output:111100 Check:1111 Correct!
Input:10000 Output:10 Check:10000 Correct!
Input:10001 Output:100010 Check:10001 Correct!
Input:10010 Output:10010 Check:10010 Correct!
Input:10011 Output:110010 Check:10011 Correct!
Input:10100 Output:1010 Check:10100 Correct!
Input:10101 Output:101010 Check:10101 Correct!
Input:10110 Output:11010 Check:10110 Correct!
Input:10111 Output:111010 Check:10111 Correct!
Input:11000 Output:110 Check:11000 Correct!
Input:11001 Output:100110 Check:11001 Correct!
Input:11010 Output:10110 Check:11010 Correct!
Input:11011 Output:110110 Check:11011 Correct!
Input:11100 Output:1110 Check:11100 Correct!
Input:11101 Output:101110 Check:11101 Correct!
Input:11110 Output:11110 Check:11110 Correct!
Input:11111 Output:111110 Check:11111 Correct!
Input:100000 Output:1 Check:100000 Correct!
Input:100001 Output:100001 Check:100001 Correct!
Input:100010 Output:10001 Check:100010 Correct!
Input:100011 Output:110001 Check:100011 Correct!
Input:100100 Output:1001 Check:100100 Correct!
Input:100101 Output:101001 Check:100101 Correct!
Input:100110 Output:11001 Check:100110 Correct!
Input:100111 Output:111001 Check:100111 Correct!
Input:101000 Output:101 Check:101000 Correct!
Input:101001 Output:100101 Check:101001 Correct!
Input:101010 Output:10101 Check:101010 Correct!
Input:101011 Output:110101 Check:101011 Correct!
Input:101100 Output:1101 Check:101100 Correct!
Input:101101 Output:101101 Check:101101 Correct!
Input:101110 Output:11101 Check:101110 Correct!
Input:101111 Output:111101 Check:101111 Correct!
Input:110000 Output:11 Check:110000 Correct!
Input:110001 Output:100011 Check:110001 Correct!
Input:110010 Output:10011 Check:110010 Correct!
Input:110011 Output:110011 Check:110011 Correct!
Input:110100 Output:1011 Check:110100 Correct!
Input:110101 Output:101011 Check:110101 Correct!
Input:110110 Output:11011 Check:110110 Correct!
Input:110111 Output:111011 Check:110111 Correct!
Input:111000 Output:111 Check:111000 Correct!
Input:111001 Output:100111 Check:111001 Correct!
Input:111010 Output:10111 Check:111010 Correct!
Input:111011 Output:110111 Check:111011 Correct!
Input:111100 Output:1111 Check:111100 Correct!
Input:111101 Output:101111 Check:111101 Correct!
Input:111110 Output:11111 Check:111110 Correct!
Input:111111 Output:111111 Check:111111 Correct!

Reversing bits in a byte is a common interview question. Though if you're asked it it's probably best to keep the inductors method to yourself  :D
Due VGA library - http://arduino.cc/forum/index.php/topic,150517.0.html


4 lengths of coax?
[ I will NOT respond to personal messages, I WILL delete them, use the forum please ]

Go Up