Binary Bit Manipulation Basics
Table of Contents
1. Intro
2. Binary Basics
3. Bit Operations
4. Permissions Example
1 - Intro
Many people take one look at bit manipulation and turn away, scared off by the seemingly complex binary knowledge needed to use it. In reality, bit manipulation is a pretty basic thing and it’s very useful. In this article I'm going to give you some basic binary knowledge and show you how to use bit manipulation operators to your advantage.
2 – Binary Basics
In order to understand how to use bitwise operators, you at least need a basic understanding of how the base-2 (binary) number system works.
I'm sure that you all know this, but just in case, a binary digit can hold 2 values: 1 or 0, or true and false respectively. This is where the base-2 name comes from, because it can hold 2 values in one digit. In a binary string you can have any amount of digits and the amount of digits it has tells the how bits it contains. So basically each digit is a bit. For example, if I had the binary string
"0001", it would be a 4 bit binary string.
Each bit of binary goes up in powers of two (1, 2, 4, 8, 16…). Therefore in a 4 bit binary string, the first bit 0000 represents 1 when it contains the value of 1 (true). The second bit (0000) represents 2. Third bit represents 4, and so on and so forth. Using that knowledge, we can derive that a 4 bit binary string, "0100", is 4 in the decimal system (base-10 if you didn't know). So that's fine, but what if we want to represent the number 3, 5, or any other non-power of 2 number? Well that's where you have to use basic addition. If I wanted the number 3 in binary, it would be "0011". This is because 2 + 1 = 3. We are taking the first bit which represents one, and the second bit which represents 2, and switching them both on. Using the same logic, if I had the binary string "1010", that would make the number 10. 8 + 2 = 10. I hope you know that.
This is one of the many ways to think of binary. If you didn't understand the way I explained it, either use one of the plentiful tutorials on Google or comment whatever you're confused about.
3 – Bit Operations
Finally, on to the thing this paper was actually meant for. So now that you know how binary works, let's get on to how we can use bitwise operators to manipulate them. In most programming languages, we have these symbols that can operate on a binary level: | (or), & (and), ^ (xor), ~ (not), and the >>/<< (shift right and left, respectively). I'm going to go through each one and explain what it does.
OR (|) – The bitwise OR compares the bits of two binary strings. Here's a demonstration of one:
0101 | 1001 = 1101
Each digit of the final output is determined by seeing if at least one of the binary strings' bit at that digit is 1. This is called OR because if a[digit] = 1 OR b[digit] = 1 then the output's bit at that digit is 1.
AND (&) – This operator also compares the bits of two binary strings. Here's a demonstration:
1101 & 1011 = 1001
If a[digit] = 1 AND b[digit] = 1 then the output's bit at that digit is one.
XOR (^) – This is a weird one. This operator sees if the bits at the current index are different and if so the output's bit at that digit is one. Example:
1100 ^ 1010 = 0110
If a[index] = 1 and b[index] = 1 then output[index] = 0. If a[index] = 0 and b[index] = 0 then output[index] = 0. If a[index] = 1 and b[index] = 0 then output[index] = 1. If a[index] = 0 and b[index] = 1 then output[index] = 1. You can also think of it as (a[index] OR b[index] but not a[index] AND b[index]).
NOT (~) – This operator is a very easy one, simply reversing all the bits of one binary string.
~1101 = 0010
Shift left/right (<</>>) – These shift the bits of one binary string right or left by a given amount.
0001 << 1 = 0010
0100 >> 2 = 0001
So there you go, an explanation of the general bitwise operations. Now on to a real life example.
4 – Permissions Example
Let's say you're programming a blog management application and want to easily set and get the permissions of some user groups [guest, writer, editor, administrator]. Well, you could do this using bit operations. Here's a sample program, in Java:
HashMap<String, Integer> users = new HashMap<String, Integer>();
HashMap<String, Integer> perms = new HashMap<String, Integer>();
int read = 1; //0001
int submit = 2; //0010
int edit = 4; //0100
int delete = 8; //1000
int guest = read; //0001
int writer = guest | submit; //0001 OR 0010 = 0011
int admin = (writer | edit) | delete; //(0011 OR 0100) OR 1000 = 1111
int mod = admin & ~(delete); //1111 AND 0111 = 0111
perms.put("Read", read);
perms.put("Submit Article", submit);
perms.put("Edit Article", edit);
perms.put("Delete Domain", delete);
users.put("Guest", guest);
users.put("Writer", writer);
users.put("Moderator", mod);
users.put("Administrator", admin);
for(int i = 0; i < users.size(); i++) {
for(int j = 0; j < perms.size(); j++) {
if((Integer.valueOf(users.values().toArray()[i].toString()) & Integer.valueOf(perms.values().toArray()[j].toString())) >= 1) {
System.out.println(users.keySet().toArray()[i] + " can " + perms.keySet().toArray()[j]);
}
}
}
Here we are creating permissions in the form of integers. We can let certain users do things through ORing them with the permissions you would like them to have because the OR operation simply switches on the bit we want. To remove a permission, like I do to the moderator, I simply AND the user with the NOT of the permission I want to delete. This essentially keeps the bits I already have the same, except for the one permission's bit which is turned off.
I hope I explained everything in a sensible manner. If I didn't please feel free to send me a PM or a message on this thread. Have a good one.
I intend to continue this with a paper on how basic mathematical operations work with binary. I will show how one would create half adders, adders, multipliers, ALUs, and maybe even a full CPU.
