• 🏆 Texturing Contest #33 is OPEN! Contestants must re-texture a SD unit model found in-game (Warcraft 3 Classic), recreating the unit into a peaceful NPC version. 🔗Click here to enter!
  • It's time for the first HD Modeling Contest of 2024. Join the theme discussion for Hive's HD Modeling Contest #6! Click here to post your idea!

Why does -14 & 0x0F == 2?

Status
Not open for further replies.
Level 15
Joined
Aug 7, 2013
Messages
1,337
Hi,

I am having trouble understanding bitwise operators. Please let me know what concept I have wrong.

-14 in in signed binary is '-0001110'. The most significant bit is 1 if the number is negative or 0 if the number is positive. Therefore we can equally represent -14 as '10001110'.

0x0F in binary is 0000 0000 0000 1111.

The & operation lines up the bits and does the following: if both bits are 1, return 1. If both bits are 0, return 0. If the bits aren't the same, return 0.

Let's line up the bit strings:

-14: 0000 0000 1000 1110
0x0F: 0000 0000 0000 1111
Result: 0000 0000 0000 1110

The result is 14 not 2. Yet my Python interpreter says it's 2:

>> -14 & 0x0F
2

I don't understand how Python got 2 instead of 14.
 
Level 29
Joined
Jul 29, 2007
Messages
5,174
-14 is actually represented as 11110010 with two's complement. I'll admit to not having any knowledge on two's complement or why it's used, but that's the explanation.
This is why you'd usually use bitwise operators with unsigned integers :)
 
Last edited:
Level 15
Joined
Aug 7, 2013
Messages
1,337
-14 is actually represented as 11110010 with two's complement. I'll admit to not having any knowledge on two's complement or why it's used, but that's the explanation.
This is why you'd usually use bitwise operators with unsigned integers :)

Python is incorrect then when it shows -14's binary representation:

>> '{:08b}'.format(-14)
'-0001110'

Well @eejin claims that Warcraft 3 corners/tiles use signed 8 bit integers when encoding flags and textures, e.g.:

JavaScript:
            int8_t texture_and_flags = reader.read<int8_t>();
            corner.ground_texture = texture_and_flags & 0x0F;

            int8_t flags = texture_and_flags & 0xF0;
            corner.ramp = flags & 0X0010;
            corner.blight = flags & 0x0020;
            corner.water = flags & 0x0040;
            corner.boundary = flags & 0x4000;

(from HiveWE/Terrain.cpp at master · stijnherfst/HiveWE · GitHub)

If the data was unsigned, he should have used uint8_t instead of int8_t. And he's doing bitwise operations on signed integers. Either this is a mistake or a quirk of how the terrain data is stored.

I think now that I understand 2's complement, my arithmetic will add up.
 

eejin

Tool Moderator
Level 12
Joined
Mar 6, 2017
Messages
221
I should've used unsigned integers, but in this case it doesn't actually matter since the underlying reader just does a dynamic reinterpretation of the raw bytes. As long as the type is 8 bits it shouldn't matter there. Now doing bit shifting might be a problem with signed integers. I'm going to change it to use unsigned types though.
 
Level 15
Joined
Aug 7, 2013
Messages
1,337
I should've used unsigned integers, but in this case it doesn't actually matter since the underlying reader just does a dynamic reinterpretation of the raw bytes. As long as the type is 8 bits it shouldn't matter there. Now doing bit shifting might be a problem with signed integers. I'm going to change it to use unsigned types though.

Thank you for clarifying this. I started running into problems when some of the values were being read as negative and I couldn't undo the bitwise operations.

Python apparently doesn't do that dynamic reinterpretation, I guess because I have to explicitly use "b" for 8 bit signed integer.

I'll change my code to also use unsigned 8 bit integers and see if this makes things work.
 

Dr Super Good

Spell Reviewer
Level 63
Joined
Jan 18, 2005
Messages
27,180
-14: 0000 0000 1000 1110
0x0F: 0000 0000 0000 1111
Result: 0000 0000 0000 1110

The result is 14 not 2. Yet my Python interpreter says it's 2:

>> -14 & 0x0F
2

I don't understand how Python got 2 instead of 14.
-14: 1111 1111 1111 0010
0x0F: 0000 0000 0000 1111
Result: 0000 0000 0000 0010 = 2

The result is 2, as thePython interpreter says:
>> -14 & 0x0F
2
Python is incorrect then when it shows -14's binary representation:

>> '{:08b}'.format(-14)
'-0001110'
This has nothing to do with Python's correctness. It is formatting it how you request it be format. That is what the format specifier does. You could also get it to format -14 into Hex, Oct or scientific notation. It might also vary the output based on locale region.

If the data was unsigned, he should have used uint8_t instead of int8_t. And he's doing bitwise operations on signed integers. Either this is a mistake or a quirk of how the terrain data is stored.
This is why you'd usually use bitwise operators with unsigned integers
Signed integers and unsigned integers work almost exactly the same for bitwise operators. The only exception is bitwise right shift which in some languages signed right shift inserts a copy of the most significant bit in order to preserve the sign while unsigned right shift always inserts a 0.

The actual question here is why on earth was -14 used?! Bitwise operator constants and magic numbers are usually entered in hexadecimal form.


0x8E: 0000 0000 1000 1110
0x0F: 0000 0000 0000 1111
Result: 0000 0000 0000 1110

The result is 14:

>> 0x8E & 0x0F
14

Thank you for clarifying this. I started running into problems when some of the values were being read as negative and I couldn't undo the bitwise operations.

Python apparently doesn't do that dynamic reinterpretation, I guess because I have to explicitly use "b" for 8 bit signed integer.

I'll change my code to also use unsigned 8 bit integers and see if this makes things work.
One can convert a signed shift into an unsigned shift using masking. One masks out the shifted bits forcing them to 0 and hence producing the same result as if an unsigned right shift was used.

Alternatively some languages that lack unsigned support, such as Java, have explicit syntax to force the use of unsigned right shift (>>>) as opposed to signed right shift (>>).

Python does not seem to be able to support unsigned right shift natively because it makes no sense to it. Bitwise right shift deletes the least significant bits from the number. When bitwise operators are performed on numbers, the smaller number is logically expanded to the length of the larger number by repeatedly appending the sign bit to the end. As such one will generally have to use natural number masks to eliminate sign bits.
I'll admit to not having any knowledge on two's complement or why it's used, but that's the explanation.
It is used for several reasons.
  • Only a single 0 value. Other sign bit approaches have two such values, 0 and -0, such as IEEE floating points. This saves a redundant numeric value increasing storage efficiency.
  • Two's Compliment integers can use the same adders and subtractors as unsigned integers. As far as these are concerned the correct answerer will be computed without doing anything special. The same hardware supports both number approaches.
  • Numeric range is approximately symmetrical around the 0 axis.
  • Simple negation logic. A positive integer can be turned negative by bitwise inversion followed by adding 1. Again this does not need special hardware as both operations work the same for unsigned integers.
This was pretty important for early computers. That said twos compliment numbers do require special multiplication, division and modulus logic compared with unsigned integers so do need special instructions to do so efficiently. Not like this made much of a difference in the old days as the computers had no such instructions and instead emulated them via software routines using bitwise operators, conditionals and addition/subtraction. Even to this day, many 8bit microcontrollers lack such instructions and still rely on software implementations.
 
Status
Not open for further replies.
Top