Functions for working with the bits of integers

[Meriipu]

there are a few functions commonly available in language specifications and standard libraries that work on the bits in integers beyond bitshifts and comparisons

I often times find these useful when working with bitmasks

gdscript has support for bitshift operations and comparisons (and, or, not, xor), but the below operations require a combination of looping or composite operations that (probably) is slower in pure gdscript without the proposed cpp backing:

• count the number of leading 0s in the binary representation of the integer N
• count the number of trailing 0s in the binary representation of the integer N
• count the number of leading 1s in the binary representation of the integer N
• count the number of trailing 1s in the binary representation of the integer N
• popcount / popcnt - returns the number of 1s in the binary representation of the integer N
• bitwise left-rotation of the integer N
• bitwise right-rotation of the integer N

Implementing these as an extension is an option in some cases, but not for web exports (sidenote: would the cpp implementation be faster for web exports or would it be slower/on par with pure gdscript ?)

[tommyettinger]

Also, there's just one right shift operator here, but there are two possible behaviors that right shifts can have (arithmetic and logical). C only performs logical shifts when operating on unsigned integers, and I'm not sure what the behavior is for a right shift in C on a negative signed integer. Java has both shifts, and even JS has both arithmetic and logical shifts, as the >> and >>> operators. Java doesn't have any unsigned types, and JS doesn't even have a true integer type in most versions. Most of the requested operations in the issue require a logical shift in their more straightforward implementations. I use arithmetic right shifts very rarely. GDScript doesn't actually completely implement either arithmetic or logical right shifts, since it just throws an error if you right-shift a negative number... And that makes most of the above common functions much harder to implement. I should also note that JS offers Math.clz32() to count leading zeros, which allows the first four methods to be implemented somewhat efficiently. Bitwise rotations do not seem possible to perform in GDScript currently because they can return negative numbers as a valid result, but not take negative numbers as input. Population count/Hamming Weight is not an uncommon operation at all, but it's possible to implement currently using Kernighan's Way, though it isn't as efficient as using a processor instruction. All of these, if they can be implemented at all, aren't as efficient as processor instructions. A GDNative extension would be great, but better still would be letting GDScript perform the same operations other languages and platforms can call efficiently.

[AThousandShips]

See also:

• Add BitMap methods for bitwise boolean operations #9609
• Enhance integer bit operations with abstractions #9480

[tommyettinger]

I wrote a little code to emulate arithmetic and logical right shifts, here. There are some other methods defined there too, including bitwise rotations. Note, I don't think these are a very good idea to include in Godot; a C++ and JS approach would be much better.