citrix interview

Next higher number with same number of binary bits set

Ans : http://www.slideshare.net/gkumar007/bits-next-higher-presentation


Program Design:

We need to note few facts of binary numbers. The expression x & -x will isolate right most set bit in x (ensuring x will use 2′s complement form for negative numbers). If we add the result to x, right most string of 1′s in x will be reset, and the immediate ’0′ left to this pattern of 1′s will be set, which is part [B] of above explanation. For example if x = 156, x & -x will result in 00000100, adding this result to x yields 10100000 (see part D). We left with the right shifting part of pattern of 1′s (part A of above explanation).

There are different ways to achieve part A. Right shifting is essentially a division operation. What should be our divisor? Clearly, it should be multiple of 2 (avoids 0.5 error in right shifting), and it should shift the right most 1′s pattern to right extreme. The expression (x & -x) will serve the purpose of divisor. An EX-OR operation between the number X and expression which is used to reset right most bits, will isolate the rightmost 1′s pattern.

A Correction Factor:

Note that we are adding right most set bit to the bit pattern. The addition operation causes a shift in the bit positions. The weight of binary system is 2, one shift causes an increase by a factor of 2. Since the increased number (rightOnesPattern in the code) being used twice, the error propagates twice. The error needs to be corrected. A right shift by 2 positions will correct the result.

The popular name for this program is same number of one bits.

#include

using namespace std;

typedef unsigned int uint_t;

// this function returns next higher number with same number of set bits as x.
uint_t snoob(uint_t x)
{

uint_t rightOne;
uint_t nextHigherOneBit;
uint_t rightOnesPattern;

uint_t next = 0;

if(x)
{

// right most set bit
rightOne = x & -(signed)x;

// reset the pattern and set next higher bit
// left part of x will be here
nextHigherOneBit = x + rightOne;

// nextHigherOneBit is now part [D] of the above explanation.

// isolate the pattern
rightOnesPattern = x ^ nextHigherOneBit;

// right adjust pattern
rightOnesPattern = (rightOnesPattern)/rightOne;

// correction factor
rightOnesPattern >>= 2;

// rightOnesPattern is now part [A] of the above explanation.

// integrate new pattern (Add [D] and [A])
next = nextHigherOneBit | rightOnesPattern;
}

return next;
}

int main()
{
int x = 156;
cout<<"Next higher number with same number of set bits is "<
getchar();
return 0;
}
Usage: Finding/Generating subsets.

Variations:

Write a program to find a number immediately smaller than given, with same number of logic 1 bits? (Pretty simple)
How to count or generate the subsets available in the given set?
References:

A nice presentation here.
Hackers Delight by Warren (An excellent and short book on various bit magic algorithms, a must for enthusiasts)
C A Reference Manual by Harbison and Steele (A good book on standard C, you can access code part of this post here).
Thanks to Venki for contribution. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.







11 comments so far

Agniswar says:
October 13, 2011 at 10:03 AM
Hi,i solved in this way..though not so efficient but pretty simple one..
Link- http://ideone.com/NBMTG

Reply
pappu says:
October 12, 2011 at 3:55 PM
int nextNumber(int x)
{
int u = log(x & -x);
int y = x >> u;
int z = log( ~y & -(~y));
int k = pow(2, z) - 1;

y = ((y >> 2) + 1) << (z + u);
return y + k;
}

Reply
AJ says:
July 26, 2011 at 10:56 PM
For immediate smaller number with same number of bits:

int next_lowest(int x)
{
int removeones = (x + 1) & x;
int isolate = removeones & ~(removeones - 1);
int shifted = (removeones ^ isolate) | (isolate >> 1);
int temp = (x + 1) & ~x;
int factor = (shifted & ~(shifted - 1)) / (temp);
int toadd = (temp - 1) * factor;

return toadd|shifted;
}
Reply
Manish Mishra says:
June 12, 2011 at 7:37 AM
To get the immediate lower number, just use this-

int nextsmallest(int n)
{
return ~nextlargest(~n);
}
Reply
Imran Amjad says:
May 31, 2011 at 4:31 PM
Hi GeeksforGeeks,

from the same logic to get the next higher number of same set bits, how i'll reverse these steps to get immediate lower number? please give a brief explanation. Thanks

Reply
sutendra mirajkar says:
April 19, 2011 at 8:39 PM
#include
#include

int main(int argc,char *argv[])
{
int a,i,temp,bin,count=0,fcount=0,flag=0;

if(argc != 2)
{
printf("IMPROPER EXECUTION,PLEASE TYPE IN THE NUMBER AFTER ./a.out_ _\n");
}

a=atoi(argv[1]);

int t=a;

while(flag == 0)
{

count=0;
for(i=8*sizeof(t)-1;i>=0;i--)
{
temp=1< bin=t & temp;
if(bin != 0)
{
if(t == a)
fcount++;
else
count++;
}
}
if(count == fcount)
{
printf("\nTHE NEXT HIGHEST NUMBER WITH SAME NO BITS TURNED ON IS:%d\n",t);
flag=1;
}
t+=1;

}

return 0;
}
Reply
naveen kolati says:
February 24, 2011 at 4:12 PM
#include
int naveen(int );
void main()
{
int p=0,k,n;
printf("enter the number");
scanf("%d",&n);
k = naveen(n);
while(k!=p)
p=naveen(++n);
printf("\n next number is %d",n);
getch();
}

int naveen(int n)
{
int count=0;
while(n!=0)
{
n=n&(n-1);
count++;
}
return count;
}
Reply
Himanshu says:
February 9, 2011 at 12:19 PM
Another method to find the lexicographical next permutation is given at following URL:

http://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation

Reply
Preetam says:
February 8, 2011 at 6:11 PM
for 5 what is the next higher number?
please write few more samples

Reply
Venki says:
February 8, 2011 at 8:50 PM
@Preetam, Use the sample program for generation of sets. You can see output for an input of 5 on http://ideone.com/W1D5E.

Reply
naveen koati says:
February 26, 2011 at 8:10 PM
6 is the next highest number after 5
6(110),5(101)

Reply
Comment

Name (Required)

Email (Required)

Website URI

Your Comment (Writing code? please paste your code between sourcecode tags)


Notify me of followup comments via e-mail

Type the two words:




Subscribe without commenting
E-Mail:



Popular Tags
GATE
Java
Dynamic Programming
Divide & Conquer
Backtracking
Pattern Searching
Operating Systems
Recursion

Forum Latest Discussion
C/ Java programming
Last Post By: Vinay
Inside: Interview Questions
Amazon Interview Question for Software Engineer/Developer (0 - 2 Years) about Al [...]
Last Post By: algogeek
Inside: Interview Questions
Reversing doubly linked list
Last Post By: kartik
Inside: Linked List specific questions
c array question
Last Post By: karthik
Inside: C/C++ Programming Questions
Microsoft Interview Question for Software Engineer/Developer (Fresher) about CPu [...]
Last Post By: karthik
Inside: Interview Questions
Directi Interview Question for Software Engineer/Developer about Aptitiude
Last Post By: Ashish
Inside: Interview Questions
Merge Vs Quick Sort
Last Post By: karthik
Inside: Java specific Questions
Adobe Interview Question for Software Engineer/Developer (Fresher) about Aptitiu [...]
Last Post By: vengat
Inside: Interview Questions
Popular Posts
The two repeating elements in an array
Tree traversal without recursion and without stack!
All permutations of a given string
Next Greater Element
Check if array elements are consecutive
The first missing number
Intersection point of two Linked Lists
Lowest Common Ancestor in a BST.
Check if a binary tree is BST or not
Median of two sorted arrays
k largest elements in an array
Forum Categories
Interview Questions
C/C++ Programming Questions
Algorithms
Trees specific questions
Linked List specific questions
Multiple Choice Questions
Object oriented queries
GPuzzles
Operating Systems
Miscellaneous
Java specific Questions
Perl specific Questions
Subscribe
Recent Comments
Arpit Gupta on Write a C program to print all permutations of a given string
venky on Remove all duplicates from the input string.
Himanshu on Check if a binary tree is subtree of another binary tree
tuhin on Run Length Encoding
dejavu on Check if a binary tree is subtree of another binary tree
dejavu on Check if a binary tree is subtree of another binary tree
Steve on Write a function to get the intersection point of two Linked Lists.
Hemil on Get Level of a node in a Binary Tree