Google Interview Question
InternsTeam: Android
Country: United States
Interview Type: In-Person
Simply count the number of 1-bits in the word. Let their number be n. The highest integer would be the one with n 1s in the more significant positions and the lowest integer would have n 1s in the less significant positions.
bit_count = 0;
while (n) {
bit_count++
n = n & (n-1)
}
largest_int = 0;
bit_count1 = bit_count;
while(bit_count1--) {
largest_int = largest_int>>>1 | 2^word_size
}
smallest_int = 0
while(bit_count--) {
smallest_int = smallest_int <<1 | 1
}
My approach would be, in order to get the next higher int, to switch the lowest '1' with the next higher '0'
Here the c# code for writing the next higher int:
private static void PrintNextHigherInteger(int i)
{
bool found = false;
int bitmask = Convert.ToInt32("1", 2);
int higher = i;
int counter = 0;
//in order to get the next higher int, switch the lowest '1' with the next higher '0'
while (true)
{
int k = higher & bitmask;
if ((higher & bitmask) != 0 && !found)
{
found = true;
higher = higher - (int) Math.Pow(2, counter);
}
else if(found)
{
//test if current bit is '0'
int test = higher << counter;
if (test % 2 == 0)
{
higher += (int) Math.Pow(2, counter);
break;
}
}
bitmask = bitmask << 1;
counter++;
}
Console.WriteLine("middle {0} - higher {1}", i, higher);
}
the next lowest int can be printed the same way. you just have to switch the lowest '1' with the next higher '0'
I don't think it is correct, for example the next higher integer for 11 (3) is 101 and not 110 like you suggest. The right heuristic is to look for the first 01 (starting from the LSB) and switch.
111010001011
^ ^
111010001101
The next lowest isn't as simple. I believe you have to find the most significant position of 10, change it to 01. However, you then have to move all remIning 1s to the right as left as possible. For example:
110 011 first becomes 101 011, but the last 011 needs to be shifted to become 110, giving 101 110.
For the next highest, you should find the first zero from LSB with the first one that appears *after* the selected zero. If not found, no solution. Similarly for the next lowest, find the first zero from LSB and swap it with the first one that appears *after* the selected one. e.g. 110011 -> next highest: 110101, next lowest: 100111
Here's some code
Wrote for next larger number, sure you can do the something similar for next smaller, didn't write it yet.
package com.interview.bits;
public class NextHigherBitDecimalEqual1 {
public static void main(String[] args) {
int a = 455;
String bits = changeBaseToStringBits(a,2);
System.out.println("a is " + a + " in bits:" + bits);
int nextHighestWithSameOnes = getNextHighestWithSameOnes(a);
String bits2 = changeBaseToStringBits(nextHighestWithSameOnes, 2);
System.out.println(nextHighestWithSameOnes + " in bits is: " + bits2);
}
private static int getNextHighestWithSameOnes(int a) {
String bits = changeBaseToStringBits(a,2);
// look for one on whose left we have zero, if found swap it. cosolidate all the ones on the right of it to the extreme right, bubbling up the ones.
// if we reach end, then add extra character:=> 1xxx=> 10xxx, corresponds to 111 => 1011, 1110 => 10011
int i = bits.length()-1;
int numberOfOnesEncountered = 0;
while(i >=0 ) {
if(i > 0 && bits.charAt(i)=='1' && bits.charAt(i-1) == '0') {
// swap i and i-1
if(i != bits.length()-1)
bits = bits.substring(0,i-1) + "10" + bits.substring(i+1);
else
bits = bits.substring(0,i-1) + "10";
break;
}
// all 1111's
// or 1 at the end like: 111000
// transform to 111 => 1011 and 111000 ==> 1011000
if(i == 0 && bits.charAt(i) == '1') {
bits = "10"+ bits.substring(1);
i = 1;
break;
}
if(bits.charAt(i) == '1') numberOfOnesEncountered++;
i--;
}
// 101100 => 110100 ==> 110001
// so basically move the i back and determine how many 1's you encounter.
int numberOfZeroesNeeded = ( bits.length()-i) - numberOfOnesEncountered; // 100110 => 101010 6 - 3 - 1 = 2
// now recreate bis add zeroes and ones as needed.
bits = bits.substring(0,i);
// add zeroes
for(; numberOfZeroesNeeded > 0 ; numberOfZeroesNeeded--, bits +="0");
for(; numberOfOnesEncountered > 0; numberOfOnesEncountered--,bits+="1");
int newNumber = convertBitStringToNum(bits);
return newNumber;
}
private static int convertBitStringToNum(String bits) {
int newNumber = 0;
int base = 1;
for(int i = bits.length()-1; i >=0; i--,base*=2) {
if(bits.charAt(i) == '1') {
newNumber += base;
}
}
return newNumber;
}
private static String changeBaseToStringBits(int a,int base) {
String bits = "";
while(a > 0) {
bits = a%base + bits;
a = a/base;
}
return bits;
}
}
Here is some code for nextSmallest integer with the same number of set bits
int nextSmallest(int n) {
int scanner = 0;
// find the first set bit in n
while ( !((n >> scanner)&1) ) {
scanner++;
}
// now skip block of consequtive 1's
while ( (n >> scanner)&1 ) {
scanner++;
}
// position to the MSB of the block of 1's
scanner--;
// reset the bit
n &= ~(1 << scanner++);
// now find the first clear bit in n
while ( (n >> scanner)&1 ) {
scanner++;
}
// set the bit
n |= (1 << scanner);
return n;
}
Few observations:
1) A number and two times of this number have the same number of 1's (multiplying shifts bit pattern by a position towards left)
2) By point 1, half of a number will also be having same number of 1's (except for those patterns which are all 1's)
3) For numbers whose bit pattern is all 1's no solution possible for "lesser than" case
A simple approach is (a) for highest number, loop over numbers from N to 2*N. Get bit representation of each number in the loop, compare number of 1's. Stop at the first match. (b) for lowest number, loop over numbers from N to N/2, get bit representation for each, compare number of 1's. Stop at the first match.
Complexity will be O(N*logN) : loop will iterate atmost N times, fetching bit representation is O(logN), comparing counts of 1's also O(logN).
//with overflow error
unsigned long long next_largest(unsigned long long n)
{
unsigned long long m = n, x = 0;
while(true)
{
if( !(n&2) && (n&1) )
return (m & ~(3<<x)) | (2<<x);
n >>= 1;
x++;
}
}
//with underflow error
unsigned long long next_smallest(unsigned long long n)
{
unsigned long long m = n, x = 0;
while(true)
{
if( (n&2) && !(n&1) )
return (m & ~(3<<x)) | (1<<x);
n >>= 1;
x++;
}
}
why not do simple logic
1. Find out number of 1 bits in number
2. test each number for number of 1 bits if same as original check with min max so far, update if more than max and lower than min
am i missing something here doesn't look me supper complicated as kind of solutions i am seeing
only have culculated the nearest high,
public static int getLowestNear(int a){
String binary = Integer.toBinaryString(a);
//add 0 at the left of the string
binary = "0"+binary;
int result = 0;
//if it is odd, then find the first 0 from the right most, position as i,
// then the nearest low is 2^i-2^(i-1)=2^(i-1),i start from 0
//if it is even, then find the first 0 after 1 from the right most, position as i.
// then the nearest low: if has 1 of 1s, 2^i-2^(i-1)=2^(i-1) ;
// if has 2 of 1s, 2^i-2^(i-1)-2^(i-2)+1=2^(i-2)+1 ;
// else 2^(i-1)+1.
if(a<=0) return 0;
if(a%2==1){
for(int i=0;i<binary.length();i++){
int index = binary.length()-i-1;
if(binary.charAt(index)=='0') {
result = a+ ((Double)(Math.pow(2,i-1))).intValue();
break;
}
}
}else{
int count=0;
int has1count = 0;
for(int i=0;i<binary.length();i++){
int index = binary.length()-i-1;
if(binary.charAt(index)=='0') {
if(has1count>0)count++;
if(count==1) {
if(has1count==1) {
result = a+ ((Double)(Math.pow(2,i-1))).intValue();
}else if(has1count==2){
result = a+ ((Double)(Math.pow(2,i-2)+1)).intValue();
}else{
result = a+ ((Double)(Math.pow(2,i-1)+1)).intValue();
}
break;
}
} else{
has1count ++;
}
}
}
return result;
}
public static int getHighNear(int a){
String binary = Integer.toBinaryString(a);
//add 0 at the left of the string
binary = "0"+binary;
int result = 0;
//if it is odd, then find the first 0 from the right most, position as i,
// then the nearest low is 2^i-2^(i-1)=2^(i-1),i start from 0
//if it is even, then find the first 0 after 1 from the right most, position as i.
// then the nearest low: 2^i-2^(i-1)-...-2^(i-n)+2^(n-1)+ ...+2^0.
// result = a+ 2^(i-min) + 2^(min-1)-1; min is min of 1s and 0s, on the right
if(a<=0) return 0;
if(a%2==1){
for(int i=0;i<binary.length();i++){
int index = binary.length()-i-1;
if(binary.charAt(index)=='0') {
result = a+ ((Double)(Math.pow(2,i-1))).intValue();
break;
}
}
}else{
int count=0;
int has0count =0;
int has1count = 0;
for(int i=0;i<binary.length();i++){
int index = binary.length()-i-1;
if(binary.charAt(index)=='0') {
if(has1count>0)count++;
has0count++;
if(count==1) {
int min = Math.min(has0count,has1count);
result = a+ ((Double)(Math.pow(2,i-min))).intValue()
+ ((Double)(Math.pow(2,min-1))).intValue()-1;
}
} else{
has1count ++;
}
}
}
return result;
}
public static int getLowNear(int a){
String binary = Integer.toBinaryString(a);
//add 0 at the left of the string
binary = "0"+binary;
int result = 0;
//if it is odd, then find the first 1 from the right most, position as i,
// then the nearest low is 2^i-2^(i-1)=2^(i-1),i start from 0
//if it is even, then find the first 1 after 0 from the right most, position as i.
// then the nearest low: 2^i-2^(i-1)-...-2^(i-n)+2^(n-1)+ ...+2^0.
// result = a- 2^(i-min) - 2^(min-1)+1; min is min of 1s and 0s, on the right
if(a<=0) return 0;
if(a%2==0){
for(int i=0;i<binary.length();i++){
int index = binary.length()-i-1;
if(binary.charAt(index)=='1') {
result = a - ((Double)(Math.pow(2,i-1))).intValue();
break;
}
}
}else{
int count=0;
int has0count =0;
int has1count = 0;
for(int i=0;i<binary.length();i++){
int index = binary.length()-i-1;
if(binary.charAt(index)=='1') {
if(has0count>0)count++;
has1count++;
if(count==1) {
int min = Math.min(has0count,has1count);
result = a- ((Double)(Math.pow(2,i-min))).intValue()
- ((Double)(Math.pow(2,min-1))).intValue()+1;
}
} else{
has0count ++;
}
}
if(has0count==1) return a;
}
return result;
}
find number of set bit. move all at least significant bit for lowest and most significant bit for highest number
void findLowHigh(int num) {
int setbits = __builtin_popcount(num);
int lowest = 0;
int highest = 0;
for(int i=0; i<setbits; ++i) {
lowest += (1<<i);
highest += (1<<(31-i));
}
cout << lowest << endl;
cout << highest << endl;
}
A solution for the next lower permutation:
int
main(int argc, char **argv)
{
unsigned v = atoi(argv[1]);
unsigned wout_trail1 = v;
unsigned trail1_marker=0, next1_marker=0;
unsigned trail1_shifted=0, next1_shifted=0;
unsigned trail1=0, trail1_shift_factor=0;
if (!v // are there any bits set
|| (v & (v+1)) == 0) { // are all the bits set
printf("no lower perm\n");
return 0;
}
// find the group of trailing 1's
if (v & 0x1) {
trail1_marker = ~v & (v + 1);
trail1 = trail1_marker - 1;
// clear the trailing 1's
wout_trail1 = v - trail1;
}
// find the next 1 bit (after clearing trailing 1's if any)
next1_marker = wout_trail1 & -wout_trail1;
// clear it
next1_shifted = wout_trail1 & ~next1_marker;
// now shift it one place right
next1_marker >>= 1;
// and put it back in the new position
// for example: 0011000 -> 0010100
next1_shifted |= next1_marker;
// shift the trailing 1's to sit right next to the "next1" bit
// for example: 001100111 -> 001111100
if (v & 0x1) {
trail1_shift_factor = next1_marker / trail1_marker;
trail1_shifted = trail1 * trail1_shift_factor;
}
// combine both parts to form the next lower permutation
v = trail1_shifted | next1_shifted;
print ("next lower: %d\n", v);
return 0;
}
here is the algorithm
switch means making 0 to 1 and 1 to zero
for next highest
------------------------
switch the lowest bit with value 0 (let it be position n) and the lowest 1 on the right side of the switched 0.
then just minimize the rest of the bits after position n.
for next lowest
---------------------
switch the highest 0 (let the position be n) and the left 1. now maximize all the bits after nth position.
minimize
---------------
switch the highest 1 (let it be position n) and lowest 0. continue to do so after n until no such is possible.
maximize
-------------
switch the highest 0 (let it be position n) and lowest 1. continue to do so after n until no such is possible.
can anyone put an efficient c or java code with this algorithm?
if we convert it to some binary string we can manipulate string easily.
just like
Integer.toBinaryString(int i)
but if anyone knows to do it by bit maniulation please share.
In this problem, we don't have to care about higher digits over the lowest 0, 1 sequence when adding 1 (or smaller numbers) to the number. For example,
11010100 --> 1101 0100 (the lowest 0,1 sequence happens in LSB+3 digit)
all we have to do is to find the next highest integer of 0100, and add 1101 on top of it.
It is because 01xx pattern can be increased to 10xx pattern and it is guaranteed that we can find 10xx pattern which has the same number of 1's as that of 01xx pattern.
(In other words, if we add too big number so that 1101 part is changed, it shouldn't be the next highest number)
For example, 0110 --> 1001, 0101 --> 1001.
Notice that we cannot use 01abcd --> 10abcd, as shown in the case 0110 --> 1001.
It is because that if we push a sequence of 1s to LSB side, we can get lower number.
For example, 011100 --> 101100 (but is this the lowest? No. push 11 to LSB) --> 100011 (now it is the lowest among all 6 digit number starting with 10 and having 3 1s)
Getting the next lowest number is similar. Just 1 and 0 exchanged.
My code is as follows:
public class JE2 {
public static void main(String[] args) {
int[] input = {0x23, // 0100 0011
0x84, // 0111 0100
0x5A, // 0101 1010
0x01, // 0000 0001
0x7FFFFFFE // 0111 1111 1111 1111 1111 1111 1111 110
};
for(int i : input) {
int low = getNextLowest(i);
int high = getNextHighest(i);
System.out.println((low != -1 ? Integer.toBinaryString(getNextLowest(i)) : "Not available")
+ " --> " + Integer.toBinaryString(i)
+ " --> " + (high != -1 ? Integer.toBinaryString(getNextHighest(i)) : "Not available"));
}
}
public static int getNextHighest(int n) {
if(n <= 0) return -1; // Assuming I'm dealing with only positive integer. Zero also excluded as it has no 1.
// read from LSB, ignore first 0 sequence, pass through 1's until finding 0.
int count0 = 0, count1 = 0;
while(n%2 == 0) {
n >>= 1;
count0++;
}
while(n%2 == 1) {
n >>= 1;
count1++;
}
if(count0 + count1 == 31) // assuming 32 bit integer, ignoring the sign bit
return -1;
n += 1; // change 0 to 1
n <<= 1 + count0; // append 1 + count0 0s
for(int i=0; i<count1-1; i++) { // append (count1 - 1) 1s
n <<= 1;
n += 1;
}
return n;
}
public static int getNextLowest(int n) {
if(n <= 0) return -1; // Assuming I'm dealing with only positive integer. Zero also excluded as it has no 1.
// read from LSB, ignore first 1 sequence, pass through 0's until finding 1.
int count0 = 0, count1 = 0;
while(n%2 == 1) {
n >>= 1;
count1++;
}
if(n == 0) return -1; // if there is no 1 any more, can't find the next lowest number with the same number of 1's
while(n%2 == 0) {
n >>= 1;
count0++;
}
n -= 1; // change 1 to 0
for(int i=0; i<count1+1; i++) { // append (count1 + 1) 1s
n <<= 1;
n += 1;
}
n <<= count0 - 1; // append count0 - 1 0s
return n;
}
}
Output is
11100 --> 100011 --> 100101
10000010 --> 10000100 --> 10001000
1011001 --> 1011010 --> 1011100
Not available --> 1 --> 10
1111111111111111111111111111101 --> 1111111111111111111111111111110 --> Not available
/**************************************************************
**
** Auto-generated to help solve interview questions.
**
** Question :
Given an integer, find the next highest and next lowest integers, with
equal number of 1s in their binary representation as the original
number.
** Carreercup Link:
careercup.com/question?id=5747769461440512
***************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <unistd.h>
int next(int x, int high)
{
int n = x, step=0, count=0, lookfor;
if(high)
lookfor = 1;
else
lookfor = 0;
while (n )
{
if( n % 2 == lookfor)
step =1;
else if ( step == 1)
{
break;
}
n = n / 2;
count ++;
}
if (high)
n = x | ( 1 << count--);
else
n = x & (~( 1 << count--));
if(high)
n = n & (~( 1 << count));
else
n = n | ( 1 << count);
return n;
}
int main()
{
int i;
for(i = 1; i <= 100; i++ )
{
printf(" value : Next = %d : %d \n", i , next(i, 0));
}
return 0;
}
from math import floor, ceil, log2
def lower_higher(n):
'''
Return the closest integers less/greater than i that have the same number of 1s as i (in binary representation)
'''
# location of the 1 in each of the following patterns
i10 = 1 # rightmost
i01 = floor(log2(n)) # leftmost
# find the location of the rightmost '10'
while not (~(n & (2**i10-1)) and (n & (2**(i10)))):
i10 += 1
# find the location of the leftmost '01'
while not (not (n & (2**i01)) and (n & (2**(i01-1)))):
i01 -= 1
# lower is simply the rightmost '10' swapped with '01'
lower = (n - (2**i10)) + 2**(i10-1)
# higher is more complicated: first swap the leftmost '10' with '01'
higher = (n + (2**i01)) - 2**(i01-1)
# count the number of ones to the left of the 10 first found
n_ones = 0
for i in range(0, i01):
if (higher >> i) & 1:
n_ones += 1
# make all those ones least significant
if n_ones > 0:
higher = (higher & ((2**ceil(log2(higher)) - 1) - (2**(i01) - 1))) | (2**(n_ones) - 1)
return lower, higher
def test_lower_higher():
assert lower_higher(5) == (3, 6)
assert lower_higher(46) == (45, 51)
assert lower_higher(0b1101101) == (0b1101011, 0b1110011)
assert lower_higher(0b1101100) == (0b1101010, 0b1110001)
assert lower_higher(0b1101000) == (0b1100100, 0b1110000)
if __name__ == '__main__':
test_lower_higher()
public static int setBit(int n, int index, boolean setBit)
{
if (setBit)
{
return (n | (1 << index));
}
else
{
int mask = ~(1 << index);
return n & mask;
}
}
public static boolean getBit(int n, int index)
{
return ((n & (1 << index)) > 0);
}
public static int getNextHigherWithSameBitString(int n)
{
int index = 0;
int ones = 0;
// find first one
while (!getBit(n, index))
{
index++;
}
// find first zero after that
while (getBit(n, index))
{
index++;
ones++;
}
// set this bit
n = setBit(n, index, true);
// unset previous bit
index--;
n = setBit(n, index, false);
ones--;
// unset prevous bits equal to number ones
for (int i = index - 1; i >= ones; i--)
{
n = setBit(n, i, false);
}
for (int i = ones - 1; i >= 0; i--)
{
n = setBit(n, i, true);
}
return n;
}
Okay, here is simple logic:
1) change the given input to binary number.
2) do the following:
def next_highest(num):
bin = dec_to_bin(num)
i = len(bin) - 1
found = False
while ( i > 0):
if bin[i] > bin[i-1]:
found = True
answer = bin[0:i-1] + bin[i] + sorted([ bin[i-1] + bin[i+1:]])
break
return bin_to_dec(answer) if found else -1
Assuming a long int here. I excluded the highest and the lowest bit (boundaries). For the rest, a simple bit shift will work I guess. Am I missing something here?
public void getNum (long num) {
long mask1 = 0x1L;
long mask2 = 1 << 63;
if ( ((num & mask1) == 0x1) || ((num & mask2) == 0x1) ) {
System.err.println ("Reached a boundary condition");
return;
} else {
System.out.println("Next higher number with same number of 1s in binary form = " + (num << 0x1));
System.out.println("Next lower number with same number of 1s in binary form = " + (num >> 0x1));
}
}
Number Properties Approach for Next Number
Observations:
»»If we “turn on” a 0, we need to “turn off” a 1
»»If we turn on a 0 at bit i and turn off a 1 at bit j, the number changes by 2^i - 2^j.
»»If we want to get a bigger number with the same number of 1s and 0s, i must be bigger than j.
Solution:
1. Traverse from right to left. Once we’ve passed a 1, turn on the next 0. We’ve now increased the number by 2^i. Yikes! Example: xxxxx011100 becomes xxxxx111100
2. Turn off the one that’s just to the right side of that. We’re now bigger by 2^i - 2^(i-1) Example: xxxxx111100 becomes xxxxx101100
3. Make the number as small as possible by rearranging all the 1s to be as far right as possible: Example: xxxxx101100 becomes xxxxx100011
To get the previous number, we do the reverse.
1. Traverse from right to left. Once we’ve passed a zero, turn off the next 1. Example: xxxxx100011 becomes xxxxx000011.
2. Turn on the 0 that is directly to the right. Example: xxxxx000011 becomes xxxxx010011.
3. Make the number as big as possible by shifting all the ones as far to the left as possible. Example: xxxxx010011 becomes xxxxx011100
public class Practice48 {
public static void main(String args[]){
int a = 48;
System.out.println("Next high is :: "+getNextHigh(a));
System.out.println("Next Low is :: "+getPrevLow(a));
}
public static int getNextHigh(int a){
int num = a;
int bit = num & 1;
int count = 0;
int flag = 1;
while(num > 0 && (bit == 1 || flag == 1)){
if(bit == 1)
flag = 0;
count++;
num = num >> 1;
bit = num & 1;
}
if(bit == 0){
int xor = (int) (Math.pow(2, count-1) + Math.pow(2, count));
a = a ^ xor;
}
num = a;
int b = 0,c = ~0;
int var = 0;
for(int i=0;i<count-1;i++){
if((num & 1) == 1){
b = b + (int)Math.pow(2, i);
}else{
var++;
}
num = num >> 1;
c = c << 1;
}
while(var > 0){
b = b >> 1;
var--;
}
return (a & c) | b;
}
public static int getPrevLow(int a){
int num = a;
int bit = num & 1;
int count = 0;
int flag = 1;
while(num > 0 && (bit == 0 || flag == 1)){
if(bit == 0)
flag = 0;
count++;
num = num >> 1;
bit = num & 1;
}
if(bit == 1){
int xor = (int) (Math.pow(2, count-1) + Math.pow(2, count));
a = a ^ xor;
}
num = a;
int b = 0,c = ~0;
int var = 0;
for(int i=0;i<count-1;i++){
if((num & 1) == 1){
b = b + (int)Math.pow(2, i);
}else{
b = b << 1;
}
num = num >> 1;
c = c << 1;
}
return (a & c) | b;
}
}
Please check "Next higher number with same number of set bits" on geeksforgeeks
- lgylym February 24, 2014