Bitwise Operators

Count Total Set Bits in All Numbers From 1 to N

Problem: Given a positive integer n, count the total number of set bits in binary representation of all numbers from 1 to n. Examples: Input: n = 3 Output: 4 Input: n = 6 Output: 9 Input: n = 7 Output: 12 Input: n = 8 Output: 13 Solution: The solution is to run a Read More →

Find the Maximum of Two Numbers Without Using if-else

Find the maximum and minimum of two integers without branching i.e. if condition. Solution: Minimum of two numbers can be found from the following: Min(x,y) = y ^ ((x ^ y) & -(x < y)) It works because if x < y, then -(x < y) will be all ones, so r = y ^ Read More →

Find the Element that Appears Once

Problem: Given an array where every element occurs three times, except one element which occurs only once. Find the element that occurs once. Expected time complexity is O(n) and O(1) extra space. Examples: Input: arr[] = {10, 1, 10, 3, 10, 1, 1, 2, 3, 3} Output: 2 Solution: If O(1) space constraint was not Read More →

Count Number of Bits to be Flipped to Convert A to B

Suppose, I have two numbers A and B. I need to find out how many numbers of bits needed to be changed to convert A to B. Like: A = 1101101 B = 1011011 ^^ ^^ Here, we need to change 4 bits to convert A to B How can I do this? Solution: 1. Read More →

Find Position of the only Set Bit

Problem: You are given a number having only one “1″ its binary representation,. You have to find position of it? Solution: First of all we will check if number is power of two, Beacuse then only its binary represenattion will contain only one “1″. After that, start from rightmost bit and one by one check Read More →

Find if a no is Power of Two

Problem: Write a C program to find if a number is of power of 2? Solution: Method 1: (Using arithmetic) Keep dividing the number by two, i.e, do n = n/2 iteratively. In any iteration, if n%2 becomes non-zero and n is not 1 then n is not a power of 2. If n becomes Read More →