"Hi, Amigo!"
"I'd also like to talk about bitmasks and XOR."
"You already know that numbers consist of bits and you can perform various operations on these bits. A bitmask is a representation of several different logical values (true/false values) as a single integer. In this case, each boolean-value corresponds to a specific bit. Here's how this could be done:"
"The binary representation of powers of two (1, 2, 4, 8, 16, 32, ...) only involves setting one bit:"
Number | Binary representation |
---|---|
1 | 0000 0001 |
2 | 0000 0010 |
4 | 0000 0100 |
8 | 0000 1000 |
16 | 0001 0000 |
19 (not a power of two) | 0001 0011 |
31 (not a power of two) | 0001 1111 |
"So, any integer can be treated as an array of bits or an array of boolean values."
"Here's how you can store different boolean values in one number:"
boolean a = true;
boolean b = false;
boolean c = true;
boolean d = false;
int result = 0;
if (a) result += 1; // 1 == 20 — bit 0
if (b) result += 2; // 2 == 21 — bit 1
if (c) result += 4; // 4 == 22 — bit 2
if (d) result += 8; // 8 == 23 — bit 3
"Now each bit is 1 if the corresponding boolean variable was true."
In our case, the variables a and c were true, so result is equal to 1+4 == 5
0000 0101
0000 dcba
"I think I know what's happening."
"Well, if you understand, let's move on."
"An int has 32 bits. One of them is used for the number's sign, and the other 31 can be used to store the values of 31 boolean variables."
"A long has 64 bits where we can store 63 boolean variables."
"Yep."
"Dozens of variables crammed into one number. That's quite a few."
"But where is this applied?"
"Mainly in situations where you need to store a lot of information about objects. When you store a lot of information about an object, there are always a couple dozen boolean variables. "With this approach, they're all conveniently stored in one number."
"With emphasis on the word 'stored'. Because actually using the number isn't so convenient."
"By the way, that's just what I wanted to ask. How do we extract the boolean value from the number?"
"It isn't complicated at all. Let's say you need to determine whether bit 6 is set to 1 (2 to the power of five is 32). We could check like this:"
int a = 32; // 25 == 0010 0000
int b = 8; // 23 == 0000 1000
int c = 2; // 21 == 0000 0010
int result = a + b + c; // 32 + 8 + 2 == 42 == 0010 1010
int a = result & 32; // 0010 1010 & 0010 0000 = 0010 0000
int b = result & 8; // 0010 1010 & 0000 1000 = 0000 1000
int c = result & 2; // 0010 1010 & 0000 0010 = 0000 0010
"Thus, working with bitmasks involves three operations:"
1) Set a specific bit to 0
2) Set a specific bit to 1
3) Check the value of the specific bit.
"Take bit 6, for example."
"How do you set bit 6 to 1?"
Code | Description |
---|---|
|
How do you set bit 6 to 1? |
|
How do you set bit 6 to 0? |
|
How do you get the value of bit 6? |
"That's highly unusual, but not difficult. Man, now I'm a hot-shot programmer."
"And one more little tip on how to easily get numbers with a specific bit set to 0 or 1: 01000000 or 10111111."
For this, we have the >> and << operators.
"1 is 2 to the zeroth power. In other words, a number with bit 0 set to 1. We need a number with bit 6 set."
int c = 1 << 6; // 0000 0001 << 6 == 0100 0000 == 64
"Cool! That's really helpful for such cases."
"But what if I need a number where every bit is set to 1 except one specific bit is set to 0?"
"That also isn't difficult:"
int d = ~(1 << 6); // ~0100 0000 == 10111111
"In other words, it's all very simple:"
Code | Description |
---|---|
|
How do you set bit 6 to 1? |
|
How do you set bit 6 to 0? |
|
How do you get the value of bit 6? |
"It doesn't look very difficult. But I won't remember it right away."
"But, if you encounter a scary expression such as "result &= ~(1 << 6)" in someone else's code, you'll know that this someone is just working with a bitmask."
"And if you encounter it often, then it will remember itself for you."
"Remember itself... That sounds good. Thank's for the lesson."
GO TO FULL VERSION