Find the maximum (or minimum) of two numbers (or morenumbers) without use of comparison operators or if-else
Posted on July 18, 2014
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
Problem Write a method which finds the maximum of two numbers You should not use if-else or any other comparison operator
EXAMPLE
Input: 5, 10
Output: 10
Solution Method 1 - Using arithematic operator
Let a is greater than b, and M is the mid point, then:
then
max = (a + b) / 2 + |a - b| / 2 Method 2 - Using most significant bit
[Read More]Find the nearest numbers that have same number of 1s for an integer
Posted on April 17, 2014
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
Problem Given an integer, print the next smallest and next largest number that have the same number of 1 bits in their binary representation.
Example
Next higher number for 3 is 5. i.e. (00000011 => 00000101)
Likewise next lower number of 5 is 3.
Solution Method 1 - Adding or subtracting 1 until we have same number of 1s
For the next largest, keep adding 1 to the number until find the number that has same number of 1 bits.
[Read More]Swap odd and even bits in an integer
Posted on March 24, 2014
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Problem
Write a program to swap odd and even bits in an integer with as few instructions as possible (e.g., bit 0 and bit 1 are swapped, bit 2 and bit 3 are swapped, etc).
Input : An integer x
Output : An integer y, which odd and even bit swapped (with 0th bit being least significant bit)
Example
Input 1: 10 = 1010 Output 1: 5 = 0101 (0th bit and 1st bit have been swapped,also 2nd and 3rd bit have been swapped) Input 2: 14 = 1110 Output 2: 13 = 1101 Solution
[Read More]Find missing integer in an array with only access to jth bit of element A[i]
Posted on March 24, 2014
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Problem
An array A[1..n] contains all the integers from 0 to n except for one number which is missing. In this problem, we cannot access an entire integer in A with a single operation. The elements of A are represented in binary, and the only operation we can use to access them is ”fetch the jth bit of A[i]”, which takes constant time. Write code to find the missing integer.
[Read More]Division without using *, / or % (Divide Two Integers)
Posted on March 23, 2014
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
Problem
Divide two integers without using multiplication, division and mod operator.
Solution
Method 1 - Subtract the number until it is less then divisor
Let a be dividend and b be divisor
public int divide(int a, int b) { if(b==0) { print("\\nDivide By Zero Error"); return Integer.MIN; } int c=0; while(a>=b) // We Repeatedly Checking for the Condition a>=b { a = a - b; // Subtract b from a, and the new result stored in 'a' itself c++; // Incrementing the Count } return c; } ```This method had been discussed [here](http://k2code.
[Read More]Count total set bits in all numbers from 1 to n
Posted on March 23, 2014
(Last modified on August 7, 2020)
| 4 minutes
| Kinshuk Chandra
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 Solutions
Method 1 - Simple - Count bits in individual number upto n
A simple solution is to run a loop from 1 to n and sum the count of set bits in all numbers from 1 to n.
[Read More]Next Power of 2
Posted on March 23, 2014
(Last modified on August 7, 2020)
| 4 minutes
| Kinshuk Chandra
Problem
Write a function that, for a given no n, finds a number p which is greater than or equal to n and is a power of 2.
Example
IP 5 OP 8 IP 17 OP 32 IP 32 OP 32 ```There are plenty of solutions for this. Let us take the example of 17 to explain some of them. Solutions **Method 0 : Multiply number by 2 until we find it** int power = 1;
[Read More]Count number of bits to be flipped to convert A to B
Posted on March 23, 2014
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Problem
You are given two numbers A and B. Write a function to determine the number of bits need to be flipped to convert integer A to integer B.
Example
Input: 73, 21 Output: 4 Representing numbers in bits : A = 1001001 B = 0010101 C = \* \*\*\* C = 4 Solution
Method 1 - Counting the bits set after XORing 2 numbers
1. Calculate XOR of A and B.
[Read More]Some useful resources
Posted on March 23, 2014
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Explain ((n & (n-1)) == 0)
Posted on March 23, 2014
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Problem :
Explain what the following code does: ((n & (n-1)) == 0).
Solution
When we have A & B == 0, it means that A and B have no common 1s, i.e. any two bits at the same positions of A and B are either different from each other, or two 0s.
It works because a binary power of two is of the form 1000...000 and subtracting one will give you 111.
[Read More]