Just what IS bitshift?

[EviTRea]

Godot Version

4.X

Question

So in the GDScript doc, there is a part that always bothers me.

Just what does this mean??
I know that using Bitflag saves memory compared to using a lot of bool, therefore good optimization under some circumstances…
No, I don’t actually know. I have no idea what it is, and I don’t know what I have to know to know what I don’t know.
There’s something very fundamental knowledge context I’m lacking here, and I don’t know what it is, it’s really annoying.

So…can anyone explain this like I’m 10?
Thanks for reading.

[TokyoFunkScene]

This answer is rooted in how computers represent numbers. You understand the concept of a 10, 9.81 or -9204e-20 just fine, but computers don’t. Computers have to use binary to represent numbers. Binary is a counting system where you only use the numbers 0 and 1 to count.

Let’s take, for example, the (decimal) number 10. In binary, this number can be represented as 0b00001010. The 0b part is a convention of notation to indicate the number we are representing is binary. (There are other counting systems that have their own prefix, like octal or hexadecimal, but let’s keep things simple for now.)

Each 0 and 1 in 0b00001010 is a bit in this number, and the number is represented with eight bits in total. Converting this number back into base 10 is a matter of performing a calculation, where you have to multiply the value of each bit with a factor of two and sum the result. The table below shows how to do this:

bit 7	bit 6	bit 5	bit 4	bit 3	bit 2	bit 1	bit 0
0	0	0	0	1	0	1	0
128	64	32	16	8	4	2	1

(0 * 128) + (0 * 64) +(0 * 32) +(0 * 16) +(1 * 8) +(0 * 4) +(1 * 2) +(0 * 1) = 10

Bit shifting does what the name implies. It shifts all of our bits in a direction we specify. Take the number 0b00001010 as an example again. If we shift the bits to the left one position, we get 0b00010100. This is equal to 20 (in decimal.)

But what is the purpose of all of this?

The answer is: don’t worry about it. You can make a game without bit shifting just fine and chances are you’ll never use it unless you’re working on something where performance is critical. Bit shifts are useful in situations where you need to squeeze every bit (ha!) of performance out of a computer, because as an operation it is very fast. But there isn’t anything a bit shift does you can’t do with code of your own.

[EviTRea]

That explains a lot, thanks.
While we’re here, can I ask what the bitwise comparison does?

[TokyoFunkScene]

As the name suggests, it’s a comparison per bit.

You’re probably already familiar with Godot’s or and and statements. Bitwise comparisons are similar to that.

Say we have two variables, a and b. A has a value of 10 and b has a value of 6. Expressed in binary: 0b00001010 and 0b00000110 respectively.

A bitwise or comparison looks at all bits of the two operands (a and b), and returns a new number where a bit is set to 1 if for one of both operands (or both) the bit in the same position is also 1. Using our example values, we get a result of 0b00001110, or 16 in decimal.

xor is an exclusive or. It’s identical to or, except a bit becomes 1 if only one of the two operands is 1. Using our example values, we get a result of 0b00001100 (or 12 in decimal.)

What and does is probably simple to figure out with all of this information.

[paintsimmon]

I typed up an explanation but tokyo answered first so here’s a fun fact:

you can swap variable’s values without using a third temp variable with bitwise XOR

[gertkeno]

Bitwise comparisons are like a boolean operation on every bit of an integer.

• & is like and
• | is like or
• ^ is “xor” exclusive or, it is similar to the != operator.

So if we treat every bit as a boolean value using and to get the final value it may look like this

  0b0011 0101    (53)
& 0b1100 0101    (197)
-------------
  0b0000 0101    (5)

Reading right-to-left the first bit between the numbers are both 1, so 1 is written to the output’s first bit. Then both bits are zero, if even one number is zero a zero will be written, similar to false and true evaluates to false. The last four bits include a one but not on both numbers, so zeros are written. Finally we end up with a much smaller value than either number.

Since the first bit represents 1 we could check for even or odd numbers by using a bitwise and on the first bit, this is a trick most compilers will recognize and do for you as it’s really fast to use bitwise operations over modulus/division.

if (my_number & 0b1) == 0:
    pass # must be even, the first bit is zero

We can see how useful bitwise AND is to Godot’s collision layer/mask system. If two objects collide we can check if their mask matches the other’s layer with a bitwise AND, if any bit matches then the collision continues.

if (self.collision_mask & other.collision_layer) != 0:
    pass # hit!

---

Bitwise OR writes 1 to the output if either numbers has 1

  0b0011 0101    (53)
| 0b1100 0101    (197)
-------------
  0b1111 0101    (245)

This is particularly useful for combining “flags”, where each bit is a boolean option combining sets of options does not overwrite or add extras. I can’t find a great example within Godot, so here’s SDL’s init sequence, each SDL_INIT_* is used to determine which sub-system needs to be loaded, without using big arrays or a long line of argument-position true/falses.

const int sdl_success = SDL_Init(SDL_INIT_VIDEO | SDL_INIT_AUDIO | SDL_INIT_GAMECONTROLLER);

---

XOR is the trickiest of the bunch, a 1 is only written if the values do not match.

  0b0011 0101    (53)
^ 0b1100 0101    (197)
-------------
  0b1111 0000    (240)

There are plenty of uses for this, fast bucket-fill algorithms, “linear feedback shift registers”, cryptography, RNG. Not sure if it’s particularly used in Godot; looks like a lot of xor-equal assignments for flags and random number generation.

[EviTRea]

ohhhhhh it returns a new value, not a true or false comparison. Got it, thanks for the explanation.

[hexgrid]

Bitwise operations are very useful and fast, once you know them.

The shift operations, for example, are equivalent to multiplying or dividing by powers of two, but are much faster than actual multiplication or division.

Bitwise comparisons are useful for packing and grouping data. Let’s say, for example, that we have some properties:

var is_flying: bool
var is_swiming: bool
var is_running: bool
var is_jumping: bool
var is_kicking: bool
var is_punching: bool
var is_shooting: bool

func is_moving() -> bool:
    if is_flying or is_swimming or is_running or is_jumping:
        return true
    return false

func is_attacking() -> bool:
    if is_kicking or is_punching or is_shooting:
        return true
    return false

We can condense that all to a state int:

const FLYING:    int = (1 << 0) # bit zero
const SWIMMING:  int = (1 << 1)
const RUNNING:   int = (1 << 2)
const JUMPING:   int = (1 << 3)
const MOVING:    int = FLYING | SWIMMING | RUNNING | JUMPING # bitwise or

const KICKING:   int = (1 << 4)
const PUNCHING:  int = (1 << 5)
const SHOOTING:  int = (1 << 6)
const ATTACKING: int = KICKING| PUNCHING | SHOOTING

var ActionMask: int

func is_moving() -> bool:
    if ActionMask & MOVING: # At least one of the bits in MOVING was set in ActionMask
        return true
    return false

func is_attacking() -> bool:
    if ActionMask & ATTACKING:
        return true
    return false

Being able to condense and group things like this means it’s easier to hand them around to other functions, and it’s easier to perform group operations.

You can also use this kind of thing for data bitmaps:

const BITMAP_X      = 64
const BITMAP_STRIDE = BITMAP_X >> 3 # Bytes per row.
const BITMAP_Y      = 64
const BITMAP_BYTES  = (BITMAP_STRIDE * BITMAP_Y) 

var Bitmap = PackedByteArray.new().resize(BITMAP_BYTES)

func bitmap_set(x: int, y: int, val: bool):
    var byte = (y * BITMAP_STRIDE) + (x >> 3) # y rows + the top bits of x
    var bit  = x & 7                          # bottom 3 bits of x

    if val: Bitmap[byte] |=  (1 << bit)
    else:   Bitmap[byte] &= ~(1 << bit) # AND with all but one bit set.

func bitmap_get(x: int, y: int) -> bool:
    var byte = (y * BITMAP_STRIDE) + (x >> 3) # y rows + the top bits of x
    var bit  = x & 7                          # bottom 3 bits of x

    return Bitmap[byte] & (1 << bit) != 0

Note that in real code you could speed this up a lot by shifting instead of multiplying if you use a power of two width for your bitmap.

There are a lot of tricks, optimizations and hacks that bitwise operations open up to you.

[EviTRea]

Godot 4 Tutorial - Bit Flags

I can finally understand the later half of this video, thanks everyone