Category: Binary

Reverse Bits of a given Integer

Given an integer, reverse its bits using binary operators.     The idea is to initialize the result by 0 (all bits 0) and process the given number starting from its least significant bit. If the current bit is 1, then we set the corresponding most significant bit in the result and finally move on …

Read More Reverse Bits of a given Integer

Huffman Coding

Huffman Coding is a algorithm for doing data compression and it forms the basic idea behind file compression. This post talks about fixed length and variable length encoding, uniquely decodable codes, prefix rules and construction of Huffman Tree.

Multiply 16-bit integers using 8-bit multiplier

Given two 16-bit positive values stored in 32-bit integer variables, find the product using the 8-bit multiply operator that that takes two 8-bit numbers and returns a 16-bit value.

Read More Multiply 16-bit integers using 8-bit multiplier

Compute parity of a number using lookup table

Given an integer, calculate its Parity. The parity refers to the number of 1’s in a given binary number.   Odd parity (encoded as 1) means there are an odd number of 1’s and even parity (encoded as 0) means that there are an even number of 1’s. Parity bits are often used as a …

Read More Compute parity of a number using lookup table

Bit Hacks – Part 6 (Random Problems)

In this post, we will discuss few unrelated problems that can be solved using bit manipulation hacks.   Below Problems are covered in this post – Problem 1. Find number of bits needed to be flipped to convert given integer to another Problem 2. Conditionally negate a value without branching Problem 3. Find XOR of …

Read More Bit Hacks – Part 6 (Random Problems)

Bit Hacks – Part 5 (Find absolute value of an integer without branching)

Given an integer, compute its absolute value (abs) without branching     We can use the expression ((n + mask) ^ mask) where mask is (n >> 31) (assuming 32 bit storage for integers) to compute the absolute value of n. The mask (n >> 31) will be evaluated to 0 for positive numbers and …

Read More Bit Hacks – Part 5 (Find absolute value of an integer without branching)