What is this code for MSBfirst/LSBfirst bit shifting doing?

Projects Programming
1

I came across this code from a blog post about the shiftOut function, apparently taken from the Arduino library in a file called wiring_shift.c:

void shiftOut(uint8_t dataPin, uint8_t clockPin, uint8_t bitOrder, uint8_t val)
{
    uint8_t i;

    for (i = 0; i < 8; i++)  {
        if (bitOrder == LSBFIRST)
            digitalWrite(dataPin, !!(val & (1 << i)));
        else
            digitalWrite(dataPin, !!(val & (1 << (7 - i))));

        digitalWrite(clockPin, HIGH);
        disgitalWrite(clockPin, LOW);
    }
}

the part that I am struggling to understand is

!!(data & (1 << i)) // for LSBFIRST

and likewise:

!!(data & (1 << (7 - i))) // for MSBFIRST

What is the purpose of the double negation operators !! here ? Is this to create some artificial delay like how inverter circuits in cascade produce some delay equal to the sum of their propagation delays ? As I tried writing my own implementation of this shiftOut function, I came up with the following:

digitalWrite(dataPin, data & 1); // extract LSB
data = data >> 1; // shift all bits to right (logical shift)

Which does the same thing but is a lot more intuitive.

2

!! turns any non zero number into a 1, without time consuming bit shifting.

3 Likes
3

It coverts the bitmask to a boolean, under the assumption that digitalWrite() wants a boolean rather than a random value. The first ! a boolean NOT; doubling it converts the boolean to the original bit sense.
(Actually these days it wants a pinstatus, so a more correct statement would be)

    digitalWrite(dataPin, (val & (1 << i)) ? HIGH : LOW);

I don't know why they shift 1 by i and do the AND vs shifting val, especially since the AVR doesn't do multibit shifts very well.

2 Likes
4

Probably not in anything that runs.

a7

5

Clever! I will have to remember that.

But if the coder who wrote shiftOut() was so concerned about bit shifting being slow, why is the for-loop coded like that? On each literation of that for-loop, that 1 gets shifted by multiple bits to make a mask to compare with val. I think a total of 7+6+...2+1 == 28 shifts will get done in total. It could have been coded so that the mask gets shifted once on each iteration, a total of 8 shifts.

EDIT: @westfw beat me to it!

1 Like
6

Hi,
very cool this feature "!!".

Look at the results:

void setup() {
 Serial.begin(115200);
 delay(100);
 Serial.print("!!34     = ");Serial.println(!!34);
 Serial.print("!!-18    = ");Serial.println(!!-18);
 Serial.print("!!'A'    = ");Serial.println(!!'A');
 Serial.print("!!string = ");Serial.println(!!"string");
 Serial.print("!!0      = ");Serial.println(!!0);
 Serial.print("!!NULL   = ");Serial.println(!!NULL);
}

void loop() {
}

!!34     = 1
!!-18    = 1
!!'A'    = 1
!!string = 1
!!0      = 0
!!NULL   = 0
7

The version on my PC is as below. No double negation and only single-bit shifts.

image

void shiftOut(uint8_t dataPin, uint8_t clockPin, uint8_t bitOrder, uint8_t val)
{
	uint8_t i;

	for (i = 0; i < 8; i++)  {
		if (bitOrder == LSBFIRST) {
			digitalWrite(dataPin, val & 1);
			val >>= 1;
		} else {	
			digitalWrite(dataPin, (val & 128) != 0);
			val <<= 1;
		}
			
		digitalWrite(clockPin, HIGH);
		digitalWrite(clockPin, LOW);		
	}
}

Actually, you can eliminate the separate mask variable by using the loop variable for that:

8 
  if (bitOrder == lsbfirst) {
    for (i = 1; i != 0; i <<= 1) {
      digitalWrite(dataPin, (val & i) ? HIGH : LOW);
      digitalWrite(clockPin_, LOW);
      digitalWrite(clockPin_, HIGH);
    }
  }

That's a nice theory, but apparently the current version of gcc will create a loop counter instead of using just the shifted value. (a 16bit loop counter at that!)
I don't know why; perhaps something to do with the loosely defined (or overly strict?) rules about integer overflows.
(heh. The other direction works fine!)

digitalWrite(dataPin, (val & 128) != 0);

I'd be really surprised if that produces better (or even different) code than !!(val &128)

If we really wanted to speed it up, we'd replace the digitalWrite() calls (but then it wouldn't be chip-independent any more :frowning: )

@NerdRalph did some Heavy duty optimization of "SPI Output" for AVR. It's both AVR specific and (muc) less general than the Arduino shiftOut, but it's probably as good as one can do (Ralph is good!)

9

This topic was automatically closed 180 days after the last reply. New replies are no longer allowed.