bitwise shift operators, where does the bit go?

Projects Programming
1

So I want to examine a byte of data and inspect the individual bits to see if they are on.

I know that I can do something like

for(byte i=0;i<8;i++)
{   if (data & (1<<i))
       do blah;
}

What I am however this seems like a lot of code to do such a simple thing. Where does the bit go that is shifted out of the byte? Does it go into overflow? I would think you could do soemthing like

for(byte i=0;i<8;i++)
{   data >>=1;
   if(overflow) {
       do blah;
   }
}

I am trying serially write to a pin and don't wish to use SPI. Speed is super important to keep the data rate as high as possible, thus, I am trying to do it with the least number of instructions.

Any help is much appreciated...

As always...
Workinonit!

2

I am trying serially write to a pin...Speed is super important to keep the data rate as high as possible, thus, I am trying to do it with the least number of instructions.

So, you are trying to write your own SoftwareSerial class?

3

Workinonit:
So I want to examine a byte of data and inspect the individual bits to see if they are on.

I know that I can do something like

for(byte i=0;i<8;i++)

{   if (data & (1<<i))
       do blah;
}




What I am however this seems like a lot of code to do such a simple thing. Where does the bit go that is shifted out of the byte? Does it go into overflow? I would think you could do soemthing like 

**Using C++ what happens on certain shift operations depends on if the variable is a signed or unsigned type (http://arduino.cc/en/Reference/Bitshift) If one is programming in AVR assembly language then you do have access to a carry and/or overflow bit that is effected by certain machine language shift and rotate instructions.**
**Lefty**

for(byte i=0;i<8;i++)
{   data >>=1;
   if(overflow) {
       do blah;
   }
}




I am trying serially write to a pin and don't wish to use SPI. Speed is super important to keep the data rate as high as possible, thus, I am trying to do it with the least number of instructions. 

Any help is much appreciated...

As always...
Workinonit!
4 
for(byte i=0;i<8;i++)
{   data >>=1;
   if(overflow) {
       do blah;
   }
}

A right shift cannot create an overflow condition. All you need to do is test the low order bit and shift the data afterwards.

for(byte i=0;i<8;i++)
{
   if(data & 1) {
       do blah;
   }
  data >>= 1;
}

If you need to test the high order bit first this code will work:

for(byte i=0;i<8;i++)
{
   if(data & 0x80) {
       do blah;
   }
  data <<= 1;
}

If data is a signed byte you can use (data < 0) instead of (data & 0x80).

Pete

5

PaulS:
So, you are trying to write your own SoftwareSerial class?

Perhaps...What I am trying to do it write to a WS2801 LED strip via pin, not with SPI. And I want to keep my refresh rate as fast as I can so I don't lose the speed of the patterns that I have with the SPI. Considering a WS2801 can support up to 24Mhz, I am thinking I should be able to write to a full 5meter strip worth of data (480) bytes with a decent refresh rate. The ADAFRUIT library that does the bit writes is terribly inefficient and I figured if I am going to write an alternative myself, I am going to do it as fast as possible. There are some strict timing issues with starting the data but then after that I think I can just push the data as fast as possible. I guess I did not think about the SoftwareSerial class, perhaps it could work? Will have to look into that.

6

el_supremo:

for(byte i=0;i<8;i++)

{   data >>=1;
   if(overflow) {
       do blah;
   }
}



A right shift cannot create an overflow condition. All you need to do is test the low order bit and shift the data *afterwards*.

for(byte i=0;i<8;i++)
{
   if(data & 1) {
       do blah;
   }
  data >>= 1;
}




If you need to test the high order bit first this code will work:

for(byte i=0;i<8;i++)
{
   if(data & 0x80) {
       do blah;
   }
  data <<= 1;
}



If data is a signed byte you can use (data < 0) instead of (data & 0x80).

Pete

How are either of those examples any different in efficiency than the first example I gave? Whether you shift the data or the comparator, the efficiency is the same. I am trying to eek a bit more time out by making use of the underlying hardware withing the processor. In assembler you to a test under mask and then branch on a condition. I was just thinking that the shift and branch on condition would be faster but perhaps I am mistaken.

7

Using C++ what happens on certain shift operations depends on if the variable is a signed or unsigned type (<< - Arduino Reference) If one is programming in AVR assembly language then you do have access to a carry and/or overflow bit that is effected by certain machine language shift and rotate instructions.
Lefty

I think this is what I am looking for. I think I need to delve into the AVR ASM stuff to get what I want. It must be possible. If its faster or not, not sure.
Thanks.

8

How are either of those examples any different in efficiency than the first example I gave?

They have two great advantages over your example.
(a) you can't access the overflow bit from C even if you use a left shift.
(b) they work.

In assembler you to a test under mask and then branch on a condition

If you are so desperate for speed you will have to use assembler, one way or another.

Pete

9

el_supremo:

How are either of those examples any different in efficiency than the first example I gave?

They have two great advantages over your example.
(a) you can't access the overflow bit from C even if you use a left shift.
(b) they work.

In assembler you to a test under mask and then branch on a condition

If you are so desperate for speed you will have to use assembler, one way or another.

Pete

I was referring to the first code snippet from my first post...

for(byte i=0;i<8;i++)
{   if (data & (1<<i))
       do blah;
}

Anyway...

Thanks for the clarification that one cannot access the overflow/carry/comparator bit in C. I was not sure if there is a definition in the libraries that could get me to it.

Is it simple to drop into asm inline in the Adruino IDE? If so, do you know how to check that bit that way?

10

You can do inline assembler stuff but the closest I have got to it is to use    asm volatile("nop\n"::);
to give me a delay guaranteed to be greater than a few nanoseconds.

You may be focusing on the wrong thing to optimize though. If your "do blah" takes microseconds or even milliseconds to execute then agonizing over the few instructions required to shift and test a bit is a waste of time.

Pete

11

Ok I think I found what I was looking for.

Here is the data sheet for the 328 pro I am looking at which as the ASM and the timings:

If I use the following

ROR - Rotate right through Carry - 1 clock cycle
BRCS - Branch if Carry Set - 1/2 clock cycle

compared with if (data & (1<<i)) the compiler probably does a

LSR - logical shift right - 1 clock
AND - and with reg - 1 clock
BRSH - branch if same or equal - 1/2 clock

So basically its 2.5 clock cycles versus 1.5 clock cycles

40% better for the check alone...

Probably splitting hairs here but there is the answer in case someone else needs it critically...

Thanks for all the help!