[TUT] Bits, Bit-fields, and Bit-wise Operators
This tutorial covers the basics of bits, bit-fields, and bit-wise operators and is written on a very basic level that everyone should be able to understand. I know a similar tutorial already exists but in my opinion it isn't very clear if the reader does not have any experience with the topic. I've also included basic examples of how bit-fields can be used in plugins. Please let me know of any errors\typos or recommendations. Also, if you've read this and are still unsure of something, please tell me so I can explain further.
What is a bit-field? A bit-field is a series of contiguous bits within a memory cell (non-array). The number of bits in a given bit-field is determined by the number of bytes allocated for the data-type being used. By default, all bits in a bit-field are 0. When no bits are 1 in a given bit-field, the resulting value will be 0. If one or more bits are 1 within a bit-field, the resulting number will be non-zero. AMX-X has only 1 data-type which is a 4-byte cell so it is limited to 32-bits in a single bit-field. If you need to manipulate bits above 32, see the bit-field array example below. Example of bit-field sizes:
All information on a computer is stored in memory (RAM, ROM, hard-disc, flash memory, etc). At the lowest level, memory consists of many many many on-off switches (known as bits). An integer value is a result of a combination of bit(s) that are set to 1 or 0. If you see me refer to a binary number, this means the bit-representation of an integer. Each bit cooresponds to a power of 2. For this example I will use 8 bits just as a quick example of how bits form a number. Bit-ordering (I'm not getting into endianness) is as follows: 7654 3210 The below values correspond to each of those bits. As you can see, if a given bit is 1 in a bitfield, the integer value will increased by the corresponding value for the respective power of 2. 1 === 2 power of 0 -- Stored in bits: 0000 0001 (binary representation) 2 === 2 power of 1 -- Stored in bits: 0000 0010 4 === 2 power of 2 -- Stored in bits: 0000 0100 8 === 2 power of 3 -- Stored in bits: 0000 1000 16 == 2 power of 4 -- Stored in bits: 0001 0000 32 == 2 power of 5 -- Stored in bits: 0010 0000 64 == 2 power of 6 -- Stored in bits: 0100 0000 128 = 2 power of 7 -- Stored in bits: 1000 0000 Suppose we have a variable holding the number 97, our bit-field would appear as: 0110 0001 Notice bits 1, 6, and 7 are set. We can then add each corresponding number (or 2 power of bit#) to our resulting number. 1 == 2 power of 0 -- 1 2 3 4 5 6 == 2 power of 5 -- 32 7 == 2 power of 6 -- 64 8 = Or 2^0 + 2^6 + 2^7 = 1 + 32 + 64 = 97 What are the bit-wise operators and how do I use them?
Operator: & Function: And Description: This operator is used to check if and only if both of the corresponding bits in both operands are 1. The resulting bit-field will consist of bits (1's) that were present at the same location within both operands. 15 & 3 = 3 15 = 0000 1111 03 = 0000 0011 03 = 0000 0011 _________________ 145 & 97 = 1 145 = 1001 0001 097 = 0110 0001 001 = 0000 0001 _________________ 255 & 234 = 234 255 = 1111 1111 234 = 1110 1010 234 = 1110 1010 Operator: | Function: Or Description: This operator is used to check if one or both bits are 1 in the corresponding bit positions of the two operands. The resulting bit-field will consist of bits (1's) that were present in either of the operands for each bit location. 15 | 3 = 15 15 = 0000 1111 03 = 0000 0011 15 = 0000 1111 _________________ 145 | 97 = 241 145 = 1001 0001 097 = 0110 0001 241 = 1111 0001 _________________ 255 | 234 = 255 255 = 1111 1111 234 = 1110 1010 255 = 1111 1111 Operator: ^ Function: Xor (Exclusive Or) Description: This operator is used to check where the corresponding bits in the two operands are different. The resulting bit-field will consist of bits (1's) that were opposite (0 & 1 or 1 & 0) at the same location within both operands. 15 ^ 3 = 12 15 = 0000 1111 03 = 0000 0011 12 = 0000 1100 _________________ 145 ^ 97 = 240 145 = 1001 0001 097 = 0110 0001 240 = 1111 0000 _________________ 255 ^ 234 = 21 255 = 1111 1111 234 = 1110 1010 021 = 0001 0101 Operator: ~ Function: Not Description: Not takes the binary representation of a number, and turns all zeros into ones, and ones into zeros. Unlike the previous 3 bitwise operators [AND, OR, XOR], NOT takes just one operand 0000 1111 = 15 1111 0000 = ~15 = 240 _________________ 1010 1010 = 170 0101 0101 = ~170 = 85 _________________ Operator: << Function: Left bit-shift Description: Shift bits in operand to the left by specified bit positions. X << Y This will shift bits in the X operand Y bits to the left. Any bits to the left that fall out of the bit-range will be dropped. Any bits added to the right due to the shift are 0. This example assumes a 1-byte memory cell so any bits shifted left past the 8th bit are dropped; if you are using a larger memory cell (in AMXX, a cell is 4-bytes or 32-bits) these bits will not be dropped but moved past the 8th bit to bits 9-32). 15 << 4 015 = 0000 1111 030 = 0001 1110 [All bits shifted 1 position] 060 = 0011 1100 [All bits shifted 2 positions] 120 = 0111 1000 [All bits shifted 3 positions] 240 = 1111 0000 [All bits shifted 4 positions] _________________ 209 << 2 209 = 1101 0001 162 = 1010 0010 [All bits shifted 1 position] 068 = 0100 0100 [All bits shifted 2 positions] Operator: >> Function: Right bit-shift Description: Shift bits in operand to the right by specified bit positions. X >> Y This will shift bits in the X operand Y bits to the right. Any bits to the right that fall out of the bit-range will be dropped. Any bits added to the left due to the shift are 0. 15 >> 4 015 = 0000 1111 007 = 0000 0111 [All bits right-shifted 1 position] 003 = 0000 0011 [All bits right-shifted 2 positions] 001 = 0000 0001 [All bits right-shifted 3 positions] 000 = 0000 0000 [All bits right-shifted 4 positions] _________________ 209 >> 2 209 = 1101 0001 104 = 0110 1000 [All bits right-shifted 1 position] 052 = 0011 0100 [All bits right-shifted 2 positions] Common bit-field operations Setting bit(s) to 1\true in a bit-field This is done using the bit-wise OR operator |. As explained above, this will set the bit to true if it exists in either operand. Assume an empty variable which we want to set bit 4 to true. Set a single bit iVariable = iVariable | ( 1 << 4 ); 0000 0000 = iVariable (freshly declared, no value set) 0001 0000 = 1 << 4 0001 0000 = iVariable | ( 1 << 4 ) Set multiple bits in the same expression iVariable = iVariable | ( ( 1 << 4 ) | ( 1 << 5 ) ) 0000 0000 = iVariable 0001 0000 = 1 << 4 0010 0000 = 1 << 5 0011 0000 = iVariable | ( ( 1 << 4 ) | ( 1 << 5 ) ) Setting bit(s) to 0\false in a bit-field This is done using a combination of bit-wise AND & and the NOT ~ operator. Assume a bit-field with bits 4 and 5 set. iVariable = ( ( 1 << 4 ) | ( 1 << 5 ) ) Suppose we need to set bit 4 to 0\false. iVariable = iVariable & ~( 1 << 4 ) 0011 0000 = ( ( 1 << 4 ) | ( 1 << 5 ) ) 1110 1111 = ~( 1 << 4 ) 0010 0000 = ( ( 1 << 4 ) | ( 1 << 5 ) ) & ~( 1 << 4 ) The same can be done for setting multiple bits to 0\false in a single expression. You only need to bit-wise OR the bits you want set to 0. iVariable = iVariable & ~( ( 1 << 4 ) | ( 1 << 5 ) ) Using bit-fields In a bit-field you can set bit(s) to 1, set bit(s) to 0, check if a particular bit(s) is 0/1, and utilize the integer that results from the bit-field. This makes bit-fields very useful and efficient. Example 1, using bit-fields as a boolean A useful application is if you want to store if a player is admin when he connects to the server. Common practice is to create an array of cells, using one cell for each player's true\false value. Boolean array method: PHP Code:
A cell is 4-bytes so using an array for this purpose requires 132 bytes of memory (33-cells times 4-bytes). If a bit-field is used instead, you will only declare a single cell and that can store the same info but using only 4 bytes! Bit-field method PHP Code:
In the situation explained above where player id's 2 and 6 are online admins, our bit-field would look like the below. If you are wondering why the bits are not at the shift position based on player id, refer to the ( id & 31 ) explained above. 0000 0000 0000 0000 0000 0000 0100 0100 A bonus for using bit-fields for storing boolean values is you can quickly check if any bits are set, or in this case, if any admins are online. Remember, if no bits are 1 in a given bit-field, the resulting value is 0; like-wise, if there are 1 or more bits set to 1 in the bit-field, the resulting number is non-zero. PHP Code:
Example 2, boolean for weapon index(s) For this example I will show how you can flag various weapons in a bit-field. This can be used in a weapon restriction plugin or any plugin that needs a true\false value for each weapon. This is possible because weapons in CS have indexes that range from 1-32. In this example we will be creating a bit-field to represent weapons CSW_SG550 [13], CSW_AWP [18], & CSW_G3SG1 [24]. The highest index for a weapon (primary\secondary) is 30 (P90) so you do not need to worry about using ( # & 31) or anything like that. g_Weapons = ( 1 << CSW_SG550 ) | ( 1 << CSW_AWP ) | ( 1 << CSW_G3SG1 ); This is what will occur with the above operation 0000 0000 0000 0000 0000 0000 0000 0001 = 1 (How 1 is represented on the bit-level. We are going to shift this bit to each weapon index bit position) 0000 0000 0000 0000 0010 0000 0000 0000 = 1 << CSW_SG550 (1 left-shifted by CSW_SG550 [13]) 0000 0000 0000 0100 0000 0000 0000 0000 = 1 << CSW_AWP (1 left-shifted by CSW_AWP [18]) 0000 0001 0000 0000 0000 0000 0000 0000 = 1 << CSW_G3SG1 (1 left-shifted by CSW_G3SG1 [24]) 0000 0001 0000 0100 0010 0000 0000 0000 = g_Weapons (The result) Remember, we are using Or for the above operation which will set each bit-position to 1 if it exists in either operand. This is why g_Weapons now has each bit set in the appropriate bit-position. Now that we have a bit-field with our desired weapons, we can then check the weapon bit with the following: PHP Code:
0000 0000 0000 0000 0000 0000 0000 0001 = 1 (Number 1 represented in bits) 0000 0000 0000 0100 0000 0000 0000 0000 = 1 << CSW_AWP (Left bit-shift of 18 bits) 0000 0001 0000 0100 0010 0000 0000 0000 = g_Weapons 0000 0000 0000 0100 0000 0000 0000 0000 = Bits in the CSW_AWP [18] position do both exist so this would return true Suppose we want to check if scout is in our bit-field. CSW_SCOUT = index 3 PHP Code:
0000 0000 0000 0000 0000 0000 0000 1000 = 1 << CSW_SCOUT (Left bit-shift of 3 bits) 0000 0001 0000 0100 0010 0000 0000 0000 = g_Weapons 0000 0000 0000 0000 0000 0000 0000 0000 = Bits in the 4th bit (1<<3) position do not both exist so this would return false Example 3, using a bit-field for your plugins flags\options. PHP Code:
PHP Code:
To easily manipulate bits in your plugin to work with players (or any 1-32 indexes) without having to re-write the bit operations each time, here are some macros. Remember, the max bit you can manipulate is 32 in AMX-X since the only data-type available is a 4-byte cell [32 bits]. PHP Code:
A major benefit is conserving memory and CPU but IMO they are, in most cases, easier than using an array of bools. As you saw towards the beginning of this tutorial, you save 131 bytes of memory by using a bit-field over an array for storing player boolean (true\false) values. It also can result in less code because you can quickly check if bits exist or not with a simple if-statement; using an array you would need some type of loop to check each element. Manipulating bits outside of the bit-range of a memory cell This can be done through the usage of a bit array. This will simply use the first array element for bits 1-32, the second element for bits 33-64, and so on. There is not max-bit limitation on a bit-array as there is with a normal bit-field. PHP Code:
PHP Code:
PHP Code:
Experimenting with binary numbers Pawn has a constant (0b) that allows you to work with values in binary directly. To use it, prefix a set of bits with 0b; the number 10 in bits is represented by 1010 so to store this value in a variable, you would do iVar = 0b1010. You can practice your knowledge using this if you are still uncomfortable after reading this tut. This functions identically to the hexadecimal prefix 0x that you may have seen used elsewhere. A few more examples: PHP Code:
PHP Code:
|
Re: [TUT] Bits, Bit-fields, and Bit-wise Operators
First. tl;dr. Will read when I get home.
|
Re: [TUT] Bits, Bit-fields, and Bit-wise Operators
Fan-fucking-tastic job, I learned a lot. Your work is appreciated, sir. :up:
|
Re: [TUT] Bits, Bit-fields, and Bit-wise Operators
Great tutorial!
Concerning bits+array: Code:
#define SetBit(%1,%2) (%1[%2>>5] |= (1<<(%2 & 31))) EDIT: oh wait, You can use SetBit(g_BitField, 0). Everything is based on 0 here like arrays. Was it confusing for anyone else? Or was I just confusing myself thinking too hard? |
Re: [TUT] Bits, Bit-fields, and Bit-wise Operators
SetBit( g_BitField , 32 ) would set the 0 ( 1 << 0 ) bit.
32 & 31 = 0 |
Re: [TUT] Bits, Bit-fields, and Bit-wise Operators
But, what I was saying is that 32>>5 is 1 right? Which puts it in the the second cell of the array. There are still 32 bits used in each cell I realize now (see my edit) since you can set SetBit(array, 0).
|
Re: [TUT] Bits, Bit-fields, and Bit-wise Operators
Quote:
|
Re: [TUT] Bits, Bit-fields, and Bit-wise Operators
Quote:
Just using it is easier than trying to understand it lol :). |
Re: [TUT] Bits, Bit-fields, and Bit-wise Operators
Okay, so I've read it and it's very detailed and explained well.
I have one thought though. Shouldn't this: Code:
Code:
|
Re: [TUT] Bits, Bit-fields, and Bit-wise Operators
Quote:
|
All times are GMT -4. The time now is 09:25. |
Powered by vBulletin®
Copyright ©2000 - 2024, vBulletin Solutions, Inc.