Lua API:Bit

From The Powder Toy
Revision as of 23:49, 1 February 2014 by boxmein (talk | contribs) (Negative numbers in binary: Formatting typo)
Jump to: navigation, search

The Bit API provides functions for performing bitwise operations on integer numbers, the Bit API is from the LuaJIT BitOp library, documentation is copied from here

If you are unfamiliar with bitwise operations, you may want to check the Wikipedia page on the subject: http://en.wikipedia.org/wiki/Bitwise_operation

Methods

Note that as the binary numbers created by bit.tobit are 4 bytes long, it's often undesirable to write out 32 bits every time a number is written. Thus I will use :: as a sort of fill-in meaning all other bits are 0.

Negative numbers in binary

For some of the functions below it's better to remember how negative numbers are most often represented in binary.

For positive numbers, it's easy enough, just keep all the bits in place and add to the rightmost bit, and as the number gets bigger, the change will trickle left as bigger and more significant bits get changed.

For negative numbers however, the usual approach is to make the leftmost bit or the most significant bit into something that keeps track of which sign the number has. This doesn't make 32 bit integers have a smaller range because of a lack of a single bit, but makes them able to represent negative numbers. Negative numbers look like this:

1 111 1101 --> -2
^ ----------- (1) 
  ^^^ ^^^^ --- (2)

(1): Sign bit. This says "Hey, the number here is negative. Just saying. Also every other bit is flipped too."

(2): Rest of the bits, except inverted. (Also called one's complement) This is to make getting the positive number back as simple as taking a binary NOT on the entire number. With a twist however - the positive number is one less from the negative number. That's because there's also a zero right in the middle of the number line.

bit.tobit

bit.tobit(number input)

Turns a number into something usable by the rest of the binary utility functions.

It converts the number into a better form (what C deems to be a signed 32-bit int) to be used by the other bit functions. If you call one of the functions below yourself however, you do not need to use this function, as the below functions already use this in their code. Here's some example values:

bit.tobit(100) --> 100
bit.tobit(-100) --> -100
bit.tobit(2147483647) --> bit.tobit(2^31 - 1) = 2147483647
bit.tobit(2147483648) --> bit.tobit(2^31) = -2147483648


bit.tohex

bit.tohex(number input, number length)

By default, length is 8, if you leave it out.
Converts its first argument to a hexadecimal representation. Returns a string.

How many hexadecimal digits to end up with is specified by the length argument. The length argument can also be negative, which specifies that the end result should have all-caps letters instead of small letters.

Examples:

bit.tohex(1) --> "00000001"
bit.tohex(0xdeadbeef) --> "deadbeef"
bit.tohex(15, 2) --> "0f"
bit.tohex(0xdeadbeef, 2) --> "ef"
bit.tohex(0xdeadbeef, -4) --> "BEEF"
bit.tohex(0xdeadbeef, 25) --> "deadbeef"


bit.bnot

bit.bnot(number input)

Returns the bitwise NOT from its argument.

What happens during a bitwise NOT looks kinda like this: you start off with a value like 25 (::00011001) and you flip every bit specially and return the value, so...

~ 0000 0000  0000 0000  0000 0000  0001 1001
= 1111 1111  1111 1111  1111 1111  1110 0110


bit.band

bit.band(number input, [number input...])

Returns the binary AND of all its arguments combined.

A binary AND is an operation that requires two numbers: the only bits that remain in the return value are ones that occur in both of the numbers. This is an easy way to pick out a single byte from a "bit string" - an integer that is actually used as a row of bits that can be used as boolean values. You can then store 32 booleans in a single int, whereas usually a single boolean is a single int!

:: 0001 1001 & 
:: 0011 0011 & 
:: 0001 1010
 = 0001 0000


bit.bor

bit.bor(number input, [number input...])

Returns the binary inclusive OR of all its arguments combined.

Binary OR is really simple: if one of the arguments has a bit there, then the end result has a bit there too. This is also a simple way to deal with flags - you'll know that a bit will be turned on if you pass it through a binary OR. Binary OR happens like so:

:: 0001 1001 |
:: 0011 1101 |
:: 0100 1000
 = 0111 1101


bit.bxor

bit.bxor(number input, [number input...])

Returns the binary exclusive OR of all its arguments combined.

Binary exclusive OR or XOR for short is interesting: the end result's bit only gets toggled on when only one of the arguments has this bit toggled on. For flags, you can utilize it to toggle a bit - if it's on it will be off and if it's off it'll be on.

:: 0011 0011 ^
:: 0010 1001 ^
:: 1100 1100 
 = 1101 0110

bit.lshift, bit.rshift, bit.arshift

bit.lshift(number input, number shift)

Shifts the input bits to the left by (shift) bits, replacing empty cells with 0 and discarding overflowing cells.

Left shifting is something really easy to imagine: every bit just gets moved once (or more) to the left and the ends are replaced with 0. If you have a bit at the far left end it gets eaten and is lost forever. Not to worry usually though.

Another great utilization of left shifting is that it's a really quick way of multiplying a number by two for some times. Shifting to the left by two is the same as multiplying a number by four.

:: 0000 0010 << 2
 = 0000 1000

Examples:

bit.lshift(2, 2) --> 8
bit.lshift(2, 34) --> 8

Important note: the shift count has to be between 1 and 32. Otherwise the number will be modulus-ed to it.


bit.rshift(number input, number shift)

Shifts the input bits to the left by (shift) bits, replacing empty cells with 0 and discarding overflowing cells.

Left shifting is something really easy to imagine: every bit just gets moved once (or more) to the left and the ends are replaced with 0. If you have a bit at the far left end it gets eaten and is lost forever. Not to worry usually though.

Another great utilization of right shifting is that it's a really quick way of dividing a number by two for some times. Shifting to the right by two is the same as dividing a number by four. Note that this will also move the sign bit. Which is what arithmetic right shift does not in fact do.

  1111 1111 :: >> 2
= 0011 1111  1100 0000 ::

Examples:

bit.rshift(-2, 5) --> 134217727
bit.rshift(4, 1) --> 2
bit.rshift(4, 33) --> 2 

Important note: the shift count has to be between 1 and 32. Otherwise the number will be modulus-ed to it.


bit.arshift(number input, number shift)

Shifts the input bits to the right by (shift) bits, copying over the sign bit for the new bits added from the left.

So the solution to our right shifting problem is that we need to add ones instead of zeros to the left side if we shift from the right. This keeps the sign right in place and still allows us to shift all we want.

  1001 1001 :: >>> 2
= 1111 1111  1100 0000 ::

Examples:

bit.arshift(-4, 1) --> -2
bit.arshift(-32, 5) --> -1
bit.arshift(32, 5) --> 1

Important note: the shift count has to be between 1 and 32. Otherwise the number will be modulus-ed to it.


bit.rol, bit.ror

bit.rol(number input, number bits)

bit.ror(number input, number bits)

Exactly like bit shifting, except it copies the bits from the right to the bits on the left instead of just feasting upon them.

:: 0000 1111 ROR 2
 = 1100 0000 :: 0000 0011
:: 1100 0011 1100 0011 ROR 2
 = 1111 0000 1111 0000 

Important note: the rotation count has to be between 1 and 32. Otherwise the number will be modulus-ed to it.

bit.bswap

bit.bswap(number input)

Swaps the byte order of the argument.

In a few places, TPT uses weird reverse-byte-order numbers, such as TPT saves in the OPS 1 format. This function makes things easier and just flips the bytes for you.

  0110 1010 0101 1001
= 1001 0101 1010 0110

Examples:

bit.tohex(bit.bswap(0x01020304)) --> "04030201"
bit.tohex(bit.bswap(0xdeadbeef), -8) --> "EFBEADDE"
bit.bswap(5) --> 83886080