shifting with negative numbers . explanation please.

Go To Last Post
18 posts / 0 new
Author
Message
#1
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

hello ,i want to ask about bitwise operators (shifting) 

 

 i know that -1 = 1th comp: 00000001

                          2th comp: 11111110

                          add 1:       11111111

and that means -1=256 in decimal here

-------

now how do i get these results after shifting with -1 (right & left shift )  ?

32<<-1 = 0 

and 32>>-1 = 64 

----

thanks in advance

Last Edited: Tue. Oct 16, 2018 - 11:20 AM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

What you are asking makes no sense. This is what the C standard says about << and >> operators:

 

 

So using an negative shift is "undefined behaviour" so no one can possibly say what the result is. If I write:

int main(void)
{
	PORTB = 3 >> -1;

the C compiler says:

		.././main.c: In function 'main':
C:\Users\uid23021\Documents\Atmel Studio\7.0\test1\test1\main.c(12,12): warning: right shift count is negative [-Wshift-count-negative]
		  PORTB = 3 >> -1;
		            ^

It did generate code however and what it generated was:

	PORTB = 3 >> -1;
  8c:	85 e2       	ldi	r24, 0x25	; 37
  8e:	90 e0       	ldi	r25, 0x00	; 0
  90:	26 e0       	ldi	r18, 0x06	; 6
  92:	fc 01       	movw	r30, r24

This is an "interesting" interpretation. The compiler has chosen to interpret >>-1 to mean <<1 in fact so the 0x03 has become 0x06

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I wonder if your original was malformed and you were actually asking what the result of something like:

-1 << 3;

was? In that case it is:

	PORTB = -1 << 3;
  8c:	85 e2       	ldi	r24, 0x25	; 37
  8e:	90 e0       	ldi	r25, 0x00	; 0
  90:	28 ef       	ldi	r18, 0xF8	; 248
  92:	fc 01       	movw	r30, r24
  94:	20 83       	st	Z, r18

so 0xFF has been shifted to 0xF8. That is 11111111 has become 11111000 - the bits shift to the left 3 places with 0 filling in behind.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

 it was shift with negative number .. 3<<-1 not -1<<3

---------

 

thank you  for answer

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

As with anything like this, if it's not covered in your copy of K&R then the next place to look is the C standard.
.
Unfortunately "undefined" means just that. In which case all you can do is just as I did and see how your own C compiler chooses to implement it.
.
(but if the code may later be used with a different compiler the fact that you are relying on non-standardized operation should be highlighted)

Last Edited: Tue. Oct 16, 2018 - 03:44 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 1

clawson wrote:
Unfortunately "undefined" means just that. In which case all you can do is just as I did and see how your own C compiler chooses to implement it.
What you can do is avoid it unless it is a documented extension.

"Undefined" can mean nasal demons of arbitrary sizes, colors

and dispositions.  The effect on one's nose is bad enough.

Any of them might take it into its head (or wherever it keeps it brain)

to go back in time and kill all your grandfathers.

Nasty business, "undefined".

"SCSI is NOT magic. There are *fundamental technical
reasons* why it is necessary to sacrifice a young
goat to your SCSI chain now and then." -- John Woods

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

skeeve wrote:
What you can do is avoid it

 

 

You can put lipstick on a pig, but it is still a pig.

I've never met a pig I didn't like, as long as you have some salt and pepper.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

first of all, you wrote:

 

I know that -1 = 1th comp: 00000001

                 2th comp: 11111110

                 add 1:    11111111

and that means -1=256 in decimal here

 

That is not true, since -1 = 255, not 256.

The problem with bit shifts on signed numbers, is that the bit 7 is the negative flag indicator.

When you shift a signed byte, the bit 7 should not be touched or considered a value bit.

 

Consider the signed byte 0011-1111 = 0x3F = +63

If you left shift, multiply by 2, it will result in 0111-1110 = 0x7E = +126, that is exactly +63 * 2

If you again left shift, it will result in 1111-1100 = 0xFC = but signed -0x7C = -124, not unsigned 252 (126*2).

 

Worse is right shifting a negative number, since bit 7 will fall into bit 6 and creating havoc with the result.

Suppose you have signed 1111-0110 = 0xF6 = -10  and you make shift right LSR.

It will end up as 0111-1011 = 0x7B = +123.

A simple LSR instruction changed the signed byte value -10 to +123.

It could mean that -10 / 2 = +124.

See how crazy it is? 

 

So, shifting signed bytes should never touch bit 7.

 

First, when shifting negative numbers the shift must be reversed.

If you use LEFT SHIFT to multiply unsigned numbers, it will divide signed numbers.

For example,

Shifting Left number 4 you get 8, number increased two fold.

Shifting Left signed number -4, you get -8, number increased negative, but as negative it was in real divided two fold.

Number -8 is smaller than -4. Well, yeah, I know.

 

Shifting signed numbers, the shift must happen only on bits 6~0.

For example, shifting RIGHT 0xC8 11000-1000 = -56 will result in -28 0xE4 1110-01000

See that bit 7 stay 1, meaning negative, bit 6 was shifted right to bit 5 and a new bit 6 appears as 1, also, bit 3 shifted to bit 2.

It means what?

The LSR and LSL instructions are no good for it, since they insert a zero bit at bit 0 or bit 7.

In this case, shifting right a signed negative byte, requires only to shift right bits 6.5.4.3.2.1.0, keeping bit 7 = 1 (negative flag) and inserting a bit 7 = 1.

 

A crude example of a RIGHT SHIFT on negative number, long explanation, would be:

 

LDI  R16, 0b11001000  ; $C8 -56

MOV  R17, R16

ANDI R17, 0b10000000  ; save bit 7 on R17 (signed flag)

LSR  R16              ; shift right all byte

ORI  R16, 0b01000000  ; insert forced bit 6 = 1

ORI  R16, R17         ; reinsert old bit 7 (signed flag)

 

The routine above will shift right R16, negative number (-56), resulting in -28 at the end.

 

The is another way to do that using the Carry bit.

LDI R16, 0b11001000

MOV R17, R16

ROL R17              ; save bit 7 in C

ROR R16              ; shift right R16 and insert old bit 7 from C

ORI R16, 0b01000000  ; force insert bit 6 = 1

 

But, as the instructions ROR, ROL, LSL, LSR works on unsigned numbers, you can convert your signed negative numbers to unsigned, subtracting them from zero, then applying the required shift and again subtracting the result from zero.  Lets see the ASR instruction later, it keeps the sign intact.

 

Example:

 

1111-1111 = -1, multiplied by 2 should be -2.

So, subtract

0000-0000 - 1111-1111 = 0000-0001

Now LSL it will become 0000-0010

Now again subtract this from zero

0000-0000 - 0000-0010 = FE 1111-1110 = -2

 

LDI R16, 0b11111111  ; 1111-1111 -1

CLR R17              ; 0000-0000

SUB R17, R16         ; 0000-0001

LSL R17              ; 0000-0010

CLR R16              ; 0000-0000

SUB R16, R17         ; 1111-1110 -2

 

Again, -3 shift left

 

LDI R16, 0b11111101  ; 1111-1101 -3

CLR R17

SUB R17, R16         ; 0000-0011

LSL R17              ; 0000-0110

CLR R16

SUB R16, R17         ; 1111-1010 -6 

 

The Z80 processor has an instruction SRA, it shifts the register to the right and keep bit 7 unchanged... specially for signed, the same as ASR in AVR cores.

The ASR (Aritmetic Shift Right) instruction shifts right all bit duplicating bit 7 in place, it allows to divide the byte by 2 and keeping the sign.  But there is no equivalent for left shift.  

 

Always remember that on 16, 24, 32 bits (multi-byte) negative numbers, only the MSB byte bit 7 is the flag. All bits (8) of the other bytes are value bits. 

Deal with negative numbers is a constant headache, our brain can't process it easily.

Every routine should stressed with all possible bit combination to make sure it works nice.

Wagner Lipnharski
Orlando Florida USA

Last Edited: Fri. Jan 11, 2019 - 04:19 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

wagnerlip wrote:

(...)

Mas, como instruções ROR, ROL, LSL, LSR são para unsigned numbers (...)

 

Huh, why does this sentence starts in portuguese then continues in english?

 

Maybe there's a glitch in the Matrixcheeky

Last Edited: Thu. Jan 10, 2019 - 01:27 AM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

El Tangas wrote:

wagnerlip wrote:

(...)

Mas, como instruções ROR, ROL, LSL, LSR são para unsigned numbers (...)

 

Huh, why does this sentence starts in portuguese then continues in english?

 

Maybe there's a glitch in the Matrixcheeky

 

Yeahhh... kkk... it happens.  I post constantly in both languages different forums... matrix got mixup. 

This week my port's nacelle is running with a subspace virus, warp coil temperature is fluctuating.   wink

 

Wagner Lipnharski
Orlando Florida USA

Last Edited: Fri. Jan 11, 2019 - 03:08 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

... of course, the raw routine posted as

 

LDI R16, 0b11111101  ; 1111-1101 -3 (create a negative number)

CLR R17

SUB R17, R16         ; 0000-0011

LSL R17              ; 0000-0110

CLR R16

SUB R16, R17         ; 1111-1010 -6 

 

could be done a little bit more efficient and elegant. since Subtracting a number from zero is exactly what the NEG (negate) instruction does, the "two's complement"

 

LDI R16, 0b11111101  ; 1111-1101 -3 (create a negative number)

NEG R16              ; 0000-0011 Subtract from zero (Two's complement)

LSL R16              ; 0000-0110 Shift Left as positive

NEG R16              ; 1111-1010 -6 

Wagner Lipnharski
Orlando Florida USA

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

 

 

But for left shift just use ADD (no need for a signed version) , and for right use ASL that will keep the correct sign.

 

Like in #11

 

LDI  R16,-3

ADD R16,R16

 

And R16 is -6

 

For AVR's with HW MUL it's sometimes better to use a signed multiplication.

 

 

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

sparrow2 wrote:

But for left shift just use ADD (no need for a signed version) , and for right use ASL that will keep the correct sign.

 

Like in #11

 

LDI  R16,-3

ADD R16,R16

 

And R16 is -6

 

For AVR's with HW MUL it's sometimes better to use a signed multiplication.

Add is what the compiler (avr-gcc 4.9.2 is the version I have here) seems to prefer.

Also, the compiler should easily optimise a multiply by power of 2 with or without hw mul.

The compiler uses add for both of these

int8_t times2(int8_t x)
{
    return x * 2;

}

int8_t times2(int8_t x)
{
    return x << 1;
}

They both give

00000080 <times2>:
  80:   88 0f           add     r24, r24
  82:   08 95           ret

And multiply by 4 gives

00000080 <times4>:
  80:   88 0f           add     r24, r24
  82:   88 0f           add     r24, r24
  84:   08 95           ret

 

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

The AVR GCC compiler use R1 as a Zero register, so it's a pain for it to use the HW mul (it will need to do a clean up) 

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

sparrow2 wrote:

The AVR GCC compiler use R1 as a Zero register, so it's a pain for it to use the HW mul (it will need to do a clean up) 

Ah, I forgot about that.

Actually, I forgot that the mega328p (which above code was compiled for) even had HW mul.

Just had to look it up.

So I was trying to use it as an example that even without HW mul, if you want to multiply by a power of 2 then there's not much point trying to be clever,  just write it as a multiply and let the compiler pick whatever it thinks is the best way to do it. Fortunately I think it still shows that :)

 

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

sparrow2 wrote:

 

 

But for left shift just use ADD (no need for a signed version) , and for right use ASL that will keep the correct sign.

 

Like in #11

 

LDI  R16,-3

ADD R16,R16

 

And R16 is -6

 

For AVR's with HW MUL it's sometimes better to use a signed multiplication.

 

 

 

The problem is that it always requires an extra byte to the left, so you can see if it still negative or not.

The quoted doesn't work very well when the value is above 64, for example, -65, when the result ends up over the limit of 7 bits for negative numbers in a single byte

LD  R16, -65  ;  1011-1111
ADD R16, R16  ;  0111-1110

R16 ends up with 0x7E what is +126 as a Byte or -130 as a word (correct). 

This is always a problem with negative numbers, the left carry can be missed, and it is NOT a missed value bit, it is the sign.

 

The other issue is that when adding the same register (multiplying by 2) of -4 (0xFC), the sign bit 7 disappears and the original bit 6 goes to 7.

But in true, this new bit 7 was originally a value bit (yellow), not a sign bit (blue).

1111-1100  

The fact that it moves to bit 7 doesn't change it color, it was a valued bit, and still being, just occupying a position of the sign bit.

carry <--- 1111-1000  

It is just coincidental that the original bit 6 was also "1" and now as bit 7 represents a negative number.

See, when it was left shifted, the original bit 7 was lost into carry, but nobody pay attention to say "oh, because the carry is on, it still a negative number".

Just the fact that the actual bit 7 is "1", everyone will say "oh, it is a negative number".

 

The -65, 1011-1111 when LEFT SHIFTED becomes

carry <--- 0111-1110, potentially a positive number since the actual bit 7 is off.

But now, everyone will cry out loud about the carry bit on... "look that, look that"..  

 

So, technically, whenever LEFT shifting signed numbers, the carry bit MUST be returned to bit 7, it should never left anyway.

 

The instruction ASR (aritmetic shift right) does exactly that for right shifting signed numbers.

 

So, the equivalent inverted ASR, would be the non existent ASL, could be always replaced by:

LSL  R16
BRCC PC+3
ORI R16,0x80
RJMP PC+2
ANDI R16,0x7F

and carry from the LSL will still be valid at output since neither ORI or ANDI touches the carry bit.

or easily as;

NEG R16
LSL
NEG R16

but here the LSL carry bit is compromised by the NEG instruction that follows.

 

Wagner Lipnharski
Orlando Florida USA

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

wagnerlip wrote:

The other issue is that when adding the same register (multiplying by 2) of -4 (0xFC), the sign bit 7 disappears and the original bit 6 goes to 7.

But in true, this new bit 7 was originally a value bit (yellow), not a sign bit (blue).

1111-1100  

The fact that it moves to bit 7 doesn't change it color, it was a valued bit, and still being, just occupying a position of the sign bit.

carry <--- 1111-1000  

It is just coincidental that the original bit 6 was also "1" and now as bit 7 represents a negative number.

 

No, it's no coincidence, it's designed like that. The largest negative number (in absolute value) that you can store in 8 bits is -128. So you can't double -65, because -130 does not fit.

But you can double -64. It's no coincidence that the binary representation of -64 is 1100 0000 so it has a "spare" 1 bit that becomes the sign after shifting. Every negative number in the range -1 to -64 will have this spare bit, so they can be doubled by shifting.

 

edit: in other words, if you have a sequence of leading "1" bits in a negative number, they are all sign bits, not just the MSB. So when you sign extend -64 to 16 bits you add 8 extra sign bits:

1100 0000 -> 1111 1111 1100 0000

Last Edited: Tue. Jan 15, 2019 - 11:22 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Your example is a overflow 

 

If there is a risk for overflow you would expand the hole thing to 16 bit. 

 

Add:

 

This is normal 2 complements algebra, not sign magnitude, so no need for any conversions.  

Last Edited: Wed. Jan 16, 2019 - 12:20 AM