Category: Binary

Find missing number and duplicate elements in an array

Given an limited range array of integers of size n with all its elements between 1 to n with the exception of one element which occur twice and one number which is missing from the list. Find missing number and the duplicate element in linear time and without using any extra memory.   For example, …

Compute Parity of a Number using Lookup Table

In this post, we will see how to compute parity of a number using lookup table. 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 …

Conditionally negate a value without branching

In this post, we will see how to conditionally negate a value without branching.   The expression ((flag^(flag-1))*n) negate n when the flag is false and the expression ((n^-flag)+flag) negate n when the flag is true.   How does it work?   1. For (flag ^ (flag – 1)) * n if flag = 0, …

Check if adjacent bits are set in binary representation of a given number

Given a number, check if adjacent bits are set in binary representation of it.   Naive Solution would be to consider every bit present in the number one by one and compare it with its previous bit. If the current bit is same as previous bit, then we have found a pair whose adjacent bits …

Bit Hacks – Part 6 (Random Problems)

In this post, we will discuss few unrelated problems that can be solved using bit manipulation hacks.   1. Find number of bits needed to be flipped to convert given integer to another The idea is to take XOR of given two integers. After calculating the XOR, the problem will reduces to counting set bits …