Difference between revisions of "Lua API:Bit"

From The Powder Toy
Jump to: navigation, search
m (→‎bit.lshift, bit.rshift, bit.arshift: fixed a typo)
(Fix description of negative numbers in binary and of some bitwise operations)
 
Line 1: Line 1:
−
The Bit API provides functions for performing bitwise operations on integer numbers, the Bit API is from the [http://bitop.luajit.org/index.html LuaJIT BitOp library], documentation is copied from [http://bitop.luajit.org/api.html here]
+
The Bit API provides functions for performing bitwise operations on integer numbers, the Bit API is from the [http://bitop.luajit.org/index.html LuaJIT BitOp library], documentation for it is [http://bitop.luajit.org/api.html 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
 
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
Line 5: Line 5:
 
== Methods ==
 
== 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.  
+
Note that as the binary numbers here are 4 bytes long, it's often undesirable to write out all 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 ===
 
=== 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 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 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:  
+
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, invert all other bits and add one. This is also called ''two's complement'' of a number, and looks like this:  
  
−
  1 111 1101 --> -2
+
    0 000 0010 -->  2  Start with positive number you want to invert
−
^ ----------- (1)  
+
1. 1 000 0010        Set the most significant bit (or ''sign bit'') to 1
−
  ^^^ ^^^^ --- (2)
+
  2. 1 111 1101         Invert all other bits
 +
3. 1 111 1110 --> -2 And, finally, add 1 to the result
 +
    ^ -------- (1)
 +
      ^^^ ^^^^ (2)
  
−
'''(1):''' Sign bit. This says "Hey, the number here is negative. Just saying. Also every other bit is flipped too."
+
'''(1):''' Sign bit. This says "Hey, the number here is negative."
 +
 
 +
'''(2):''' Rest of the bits.
 +
 
 +
This allows addition and subtraction of binary numbers without needing to worry about sign bit and overflows. For example, if you want to add numbers -2 and 5, you can do it like this: (4 bits for shortness)
 +
 
 +
  1 110 --> -2
 +
+ 0 101 -->  5
 +
 
 +
1. 0 + 1 = 1, set first bit of result to 1
 +
2. 1 + 0 = 1, set second bit of result to 1
 +
3. 1 + 1 = 2, but since 2 is greater than 1 set third bit of result to 0 and add 1 to the next bit
 +
4. 1 + 0 and + 1 more = 2, again greater than 1, so set fourth bit of result to 0, but since this is the sign bit ignore the overflow
 +
 
 +
= 0 011 -->  3
 +
 
 +
To learn more about it, check the Wikipedia page for ''two's complement'': https://en.wikipedia.org/wiki/Two%27s_complement
  
−
'''(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 ===
Line 27: Line 45:
 
<code>bit.tobit(number input)</code>
 
<code>bit.tobit(number input)</code>
  
−
Turns a number into something usable by the rest of the binary utility functions.
+
Converts a 64-bit integer into a 32-bit integer by removing all bits above 32nd. You do not need to use this function, as the below functions will do this automatically. Here's some example values:
−
 
 
−
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
Line 54: Line 70:
 
  bit.tohex(0xdeadbeef, -4) --> "BEEF"
 
  bit.tohex(0xdeadbeef, -4) --> "BEEF"
 
  bit.tohex(0xdeadbeef, 25) --> "deadbeef"
 
  bit.tohex(0xdeadbeef, 25) --> "deadbeef"
−
 
  
  
Line 75: Line 90:
 
Returns the binary AND of all its arguments combined.  
 
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!
+
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 bit 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 8 booleans in a single byte, whereas usually a single boolean is a single byte!
  
 
  :: 0001 1001 &  
 
  :: 0001 1001 &  
Line 118: Line 133:
 
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.  
 
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.
+
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. Note that this performs logical shift meaning that it will also move the ''sign bit''.
  
 
  :: 0000 0010 << 2
 
  :: 0000 0010 << 2
Line 138: Line 153:
 
Right shifting is something really easy to imagine: every bit just gets moved once (or more) to the right and the ends are replaced with 0. If you have a bit at the far right end it gets eaten and is lost forever. Not to worry usually though.  
 
Right shifting is something really easy to imagine: every bit just gets moved once (or more) to the right and the ends are replaced with 0. If you have a bit at the far right 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.
+
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 performs logical shift meaning that it will also move the ''sign bit''.
  
−
  &nbsp;&nbsp;1111 1111 :: >> 2
+
  &nbsp;&nbsp;1111 1111 :: >>> 2
 
  = 0011 1111  1100 0000 ::
 
  = 0011 1111  1100 0000 ::
  
Line 155: Line 170:
 
<code>bit.arshift(number input, number shift)</code>
 
<code>bit.arshift(number input, number shift)</code>
  
−
Shifts the input bits to the right by (shift) bits, copying over the sign bit for the new bits added from the left.
+
Shifts the input bits to the right by (shift) bits, copying over the sign bit for the new bits added from the left. This keeps the sign right in place and still allows us to shift all we want.
−
 
 
−
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.  
 
  
−
  &nbsp;&nbsp;1001 1001  0000 0000 :: >>> 2
+
  &nbsp;&nbsp;1001 1001  0000 0000 :: >> 2
 
  = 1110 0110  0100 0000 ::
 
  = 1110 0110  0100 0000 ::
  
Line 189: Line 202:
 
<code>bit.bswap(number input)</code>
 
<code>bit.bswap(number input)</code>
  
−
Swaps the '''byte''' order of the argument.
+
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.  
+
In a some places, TPT uses low-endian (least significant byte on the left) instead of usually used big-endian (most significant byte on the left) order of bytes, such as in TPT saves in the OPS 1 format. This function makes things easier and just flips the byte order for you.
  
 
  &nbsp; 0110 1010 0101 1001
 
  &nbsp; 0110 1010 0101 1001

Latest revision as of 18:00, 19 August 2024

The Bit API provides functions for performing bitwise operations on integer numbers, the Bit API is from the LuaJIT BitOp library, documentation for it is 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 here are 4 bytes long, it's often undesirable to write out all 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, invert all other bits and add one. This is also called two's complement of a number, and looks like this: 

   0 000 0010 -->  2  Start with positive number you want to invert
1. 1 000 0010         Set the most significant bit (or sign bit) to 1
2. 1 111 1101         Invert all other bits
3. 1 111 1110 --> -2  And, finally, add 1 to the result
   ^ -------- (1)
     ^^^ ^^^^ (2)

(1): Sign bit. This says "Hey, the number here is negative."

(2): Rest of the bits.

This allows addition and subtraction of binary numbers without needing to worry about sign bit and overflows. For example, if you want to add numbers -2 and 5, you can do it like this: (4 bits for shortness) 

  1 110 --> -2
+ 0 101 -->  5

1. 0 + 1 = 1, set first bit of result to 1
2. 1 + 0 = 1, set second bit of result to 1
3. 1 + 1 = 2, but since 2 is greater than 1 set third bit of result to 0 and add 1 to the next bit
4. 1 + 0 and + 1 more = 2, again greater than 1, so set fourth bit of result to 0, but since this is the sign bit ignore the overflow

= 0 011 -->  3

To learn more about it, check the Wikipedia page for two's complement: https://en.wikipedia.org/wiki/Two%27s_complement


bit.tobit

bit.tobit(number input)

Converts a 64-bit integer into a 32-bit integer by removing all bits above 32nd. You do not need to use this function, as the below functions will do this automatically. 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 bit 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 8 booleans in a single byte, whereas usually a single boolean is a single byte! 

:: 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. Note that this performs logical shift meaning that it will also move the sign bit. 

:: 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 right by (shift) bits, replacing empty cells with 0 and discarding overflowing cells.

Right shifting is something really easy to imagine: every bit just gets moved once (or more) to the right and the ends are replaced with 0. If you have a bit at the far right 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 performs logical shift meaning that it will also move the sign bit. 

  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. This keeps the sign right in place and still allows us to shift all we want. 

  1001 1001  0000 0000 :: >> 2
= 1110 0110  0100 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 some places, TPT uses low-endian (least significant byte on the left) instead of usually used big-endian (most significant byte on the left) order of bytes, such as in TPT saves in the OPS 1 format. This function makes things easier and just flips the byte order 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
Retrieved from "https://powdertoy.co.uk/Wiki/index.php?title=Lua_API:Bit&oldid=9359"