## Brian Kernighanâ€™s Algorithm to count set bits in an integer

Given an integer, count its set bits.

Coding made easy

Given an integer, count its set bits.

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, …

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 …

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 …

Write a program to find XOR of two numbers without using XOR operator. Naive Solution would be to consider every bit present in both numbers one by one (either from left or right) and compare them. If the current bit is same in both numbers (i.e. both are 0 or both are 1), we …

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 …

In this post we will discuss some of the bit hacks/tricks on letters of English alphabet. Below tricks are covered in this post – Trick 1. Convert uppercase character to lowercase Trick 2. Convert lowercase character to uppercase Trick 3. Invert alphabet’s case Trick 4. Find letter’s position in alphabet Trick 1. …

In this post we will discuss few related problems that are related to unsetting the rightmost set bit of a number. How to unset the rightmost set bit of a number? The expression (n & (n – 1)) will turn off the rightmost set bit of given number. (n – 1) will have all …

In this post we will discuss few related problems that operates on the k’th bit of a number. Below problems are covered in this post – Problem 1. Turn off kth bit in a number Problem 2. Turn on kth bit in a number Problem 3. Check if kth bit is set for a …

With this post, we will start a series of amazing bit manipulation hacks that every programmer should know. Below problems are covered in this post – Problem 1. Check if an given integer is even or odd Problem 2. Detect if two integers have opposite signs or not Problem 3. Add 1 to a …

Given two integers x and n where n is non-negative, efficiently compute the value of power function pow(x, n).

Given an array of integers, find out minimum and maximum element present using minimum comparisons.