Difference between revisions of "Lua API:Bit"

From The Powder Toy
Jump to: navigation, search
m (Lua category)
(Fix description of negative numbers in binary and of some bitwise operations)
 
(4 intermediate revisions by 2 users not shown)
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
  
 
== Methods ==
 
== 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 bit.tobit(number input)
+
 
−
Normalizes a number to the numeric range for bit operations and returns it. This function is usually not needed since all bit operations already normalize all of their input arguments.
+
<code>bit.tobit(number input)</code>
 +
 
 +
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 ===
−
string bit.tohex(number input, [number length = 8])
+
 
−
Converts its first argument to a hex string. The number of hex digits is given by the absolute value of the optional second argument. Positive numbers between 1 and 8 generate lowercase hex digits. Negative numbers generate uppercase hex digits. Only the least-significant 4*|n| bits are used. The default is to generate 8 lowercase hex digits.
+
<code>bit.tohex(number input, number length)</code>
 +
 
 +
'''By default, length is 8, if you leave it out.'''<br />
 +
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 bit.bnot(number input)
+
 
−
Returns the bitwise not of its argument.
+
<code>bit.bnot(number input)</code>
−
=== bit.band, bit.bor, bit.bxor ===
+
 
−
number bit.bor(number input, [number input...])
+
Returns the bitwise NOT from its argument.
−
  number bit.band(number input, [number input...])
+
 
−
  number bit.bxor(number input, [number input...])
+
What happens during a bitwise NOT looks kinda like this: you start off with a value like 25 (<code>::00011001</code>) and you flip every bit specially and return the value, so...
−
Returns either the bitwise or, bitwise and, or bitwise xor of all of its arguments. Note that more than two arguments are allowed.
+
 
 +
~ 0000 0000  0000 0000  0000 0000  0001 1001
 +
= 1111 1111  1111 1111  1111 1111  1110 0110
 +
 
 +
 
 +
=== bit.band ===
 +
 
 +
<code>bit.band(number input, [number input...])</code>
 +
 
 +
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
 +
  &nbsp;= 0001 0000
 +
 
 +
 
 +
=== bit.bor ===
 +
 
 +
<code>bit.bor(number input, [number input...])</code>
 +
 
 +
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
 +
  &nbsp;= 0111 1101
 +
 
 +
 
 +
=== bit.bxor ===
 +
 
 +
<code>bit.bxor(number input, [number input...])</code>
 +
 
 +
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
 +
&nbsp;= 1101 0110
 +
 
 
=== bit.lshift, bit.rshift, bit.arshift ===
 
=== bit.lshift, bit.rshift, bit.arshift ===
−
number bit.lshift(number input, number shift)
+
 
−
  number bit.rshift(number input, number shift)
+
<code>bit.lshift(number input, number shift)</code>
−
  number bit.arshift(number input, number shift)
+
 
−
Returns either the bitwise logical left-shift, bitwise logical right-shift, or bitwise arithmetic right-shift of its first argument by the number of bits given by the second argument.
+
Shifts the input bits to the left by (shift) bits, replacing empty cells with 0 and discarding overflowing cells.
−
Logical shifts treat the first argument as an unsigned number and shift in 0-bits. Arithmetic right-shift treats the most-significant bit as a sign bit and replicates it.
+
 
−
Only the lower 5 bits of the shift count are used (reduces to the range [0..31]).
+
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
 +
&nbsp;= 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.'''
 +
 
 +
 
 +
 
 +
<code>bit.rshift(number input, number shift)</code>
 +
 
 +
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''.
 +
 
 +
&nbsp;&nbsp;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.'''
 +
 
 +
 
 +
 
 +
<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. This keeps the sign right in place and still allows us to shift all we want.
 +
 
 +
&nbsp;&nbsp;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, bit.ror ===
−
number bit.rol(number input, number bits)
+
 
−
number bit.ror(number input, number bits)
+
<code>bit.rol(number input, number bits)</code>
−
Returns either the bitwise left rotation, or bitwise right rotation of its first argument by the number of bits given by the second argument. Bits shifted out on one side are shifted back in on the other side.
+
 
−
Only the lower 5 bits of the rotate count are used (reduces to the range [0..31]).
+
<code>bit.ror(number input, number bits)</code>
 +
 
 +
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
 +
&nbsp;= 1100 0000 :: 0000 0011
 +
:: 1100 0011 1100 0011 ROR 2
 +
&nbsp;= 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 bit.bswap(number input)
+
 
−
Swaps the bytes of its argument and returns it. This can be used to convert little-endian 32 bit numbers to big-endian 32 bit numbers or vice versa.
+
<code>bit.bswap(number input)</code>
 +
 
 +
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.
 +
 
 +
&nbsp; 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
 +
 
  
 
[[Category:Lua]]
 
[[Category:Lua]]

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"