This content originally appeared on Level Up Coding - Medium and was authored by Prachi Jamdade
Hey All 👋,
In this article, I will take you through one of the most important and interesting topics — Bit Manipulation!
A bit is the smallest unit of data or information. A bit has a single binary value either 0 or 1. Bit manipulation is a technique of applying logical operations on a sequence of bits to achieve a required result. But why bitwise operations are important?
We think that the main use of bit manipulation is to substitute arithmetic operations. But it’s not true. Bitwise operations have many applications. Cryptography, computer graphics, hash functions, digital image processing, compression algorithms, and network protocols are just some examples where bitwise operations are extremely useful.
Bit manipulations tips and tricks will also help you in Competitive Programming as well. Using bitwise operators in competitive programming can help in speeding up the code. Bit manipulation has constant time complexity. The computations performed directly on bits are quite fast, hence improving system performance.
Now, let’s look at a few bit manipulation tips and tricks. You can apply these tricks in your day-to-day coding tasks 😉.
You should know binary number system and bitwise operators such as AND, OR, NOT, XOR, Right Shift and Left Shift (&, |, ~, ^, >>, <<) as a prerequisite.
- The fastest way to swap two numbers.
We often came across such coding problems where swapping is required. In that case, what usually we do is to use a temporary variable to swap the numbers.
You can do the same job using XOR. Let’s see how :
- Quickly check if a number is odd or even.
Normally, what we do is divide the number by 2, if its remainder is 0 then the number is divisible by 2, else the number is not divisible by 2. But do you think that this is the fastest method to check the divisibility of a number by 2? No, it’s not!
Here is what we can do using bitwise operators. Just perform bitwise AND of a number by 1. If (n & 1) returns 1 then the number is not divisible by 2. Otherwise yes it is divisible.
- Magical XOR Operator.
The bitwise XOR operator is used in many coding problems. A simple example could be “Given a set of numbers where all elements occur an even number of times except one number, find the odd occurring number”. You can easily solve this problem by just doing XOR to all numbers.
If we take XOR of zero and some bit, it will return that bit: a ^ 0 = a
If we take XOR of two same bits, it will return 0: a ^ a = 0
For n numbers, the below math can be applied: a ^ b ^ a = (a ^ a) ^ b = 0 ^ b = b
- Convert Upper case alphabets to Lower case and vice versa.
Bit representation of English alphabets -
A -> 01000001 a -> 01100001
B -> 01000010 b -> 01100010
C -> 01000011 c -> 01100011
........ ........
Y -> 01011001 y -> 01111001
Z -> 01011010 z -> 01111010
The binary representation of lowercase and uppercase letters are nearly identical, with only 1 bit of difference.
By doing XOR operation we toggle that single bit and swap it to the opposite value. It will convert the uppercase alphabet to lowercase and vice versa.
You can convert any character, ch, to the opposite case by doingch ^= 32.
- What can you do using Right Shift and Left Shift operators?
Shifting the bits of an integer number left by one place is equivalent to multiplying the number by 2, while shifting them one place to the right is equivalent to dividing the number by 2.
Left shifting an integer ‘a’ with an integer ‘b’ (a << b) is equivalent to multiplying x with 2 ^ b (2 raise to power b).
Similarly, (a >> b) is equivalent to dividing x with 2 ^ b.
I hope you learned something new by the end of this article. Use these tricks in your daily coding 😉.
If you found this article insightful, give it a clap.
Happy Learning!
Level Up Coding
Thanks for being a part of our community! More content in the Level Up Coding publication.
Follow: Twitter, LinkedIn, Newsletter
Level Up is transforming tech recruiting ➡️ Join our talent collective
Bit Manipulation Tips and Tricks You Should Know was originally published in Level Up Coding on Medium, where people are continuing the conversation by highlighting and responding to this story.
This content originally appeared on Level Up Coding - Medium and was authored by Prachi Jamdade
Prachi Jamdade | Sciencx (2022-06-27T11:12:30+00:00) Bit Manipulation Tips and Tricks You Should Know. Retrieved from https://www.scien.cx/2022/06/27/bit-manipulation-tips-and-tricks-you-should-know/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.