CareerCup

Finding out the number of 1s in a given number n:

count = 0;

while(n) {
count++
n = n & (n-1)
}

Next integer having the same number of 1s in a given n:

Starting from the rightmost 1, traverse the bits to it's left to find the rightmost 0. Swap the 0 bit with the 1 bit to it's right.

i = 0
while (!(n & ( 1 << i ))) { i++}
while (n | ( 1 << i )) { i++}
n = n | (1 << i)
n = n & ~(1 << (i-1))

Java Coding Question

The following code finds the next highest and prev lowest number that contains the same number of 1's as the given number.

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

package GoodProbs;

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; 
	}
}

Here is java code for both the questions

for number greater than given integer.
Here we just have to transfer the bit position of first '1' to next immediate position.
steps:
1) find first '1' in the binary representation of the given integer (from left side)
2) if it next bit is '0' then set it '1' and the previous bit (which is '1' ) to '0'.

public static int noOfOne(int n){
		int count = 0;
		for (; n != 0; n = n>>1){
			if ((n & 1) == 1){
				count++;	
			}
		}
		return count;
	}

	
	public static int nextNumber (int n){
		int flag = 0;
		int num = n;
		int countOne = noOfOne(n);
		if (countOne > 0){	
			for (int i=num, j=1; i!=0; i = i>>1, j=j<<1){
				if ((i&1) == 1){
					if (flag == 1){
						flag = 0;
					}else{
						flag = 1;
					}	
				}else{
					if (flag == 1){
						n = n | j;
						j = j>>1;
						n = n^j;
						break;
					}
				}	
			}
		}	
		return n;

}

Following is my solution in Java by using Murali Mohan suggestion to find out next big number having same number of binary 1's.

public void findOnes(int n){
		String re="";
		int count=0;
		while(n>0){
			re = (n%2)+re;
			if(n%2==1){
				count++;
			}
			n=n/2;
		}
		re=n+re;
		System.out.println(count);
		System.out.println(re);
		char ch[] = re.toCharArray();
		for(int i=ch.length-1;i>=0;i--){
			if(ch[i]=='0'){
				ch[i]='1';
				ch[i+1]='0';
			}
		}
		System.out.println(ch);
		n=0;
		int k=1;
		for(int i=ch.length;i>=1;i--){
			if(ch[i-1]=='1'){
				n += k;
			}
			k=k*2;
		}
		System.out.println(n);
	}

In python:

#!/usr/bin/python

n=101
b=bin(n)
print(b)
l=list(b)

del l[0]
l.remove('b')
e=len(l)

l.reverse()
i=0

while (i<len(l)) :

if l[i]=='1' and l[i+1]=='0' :
        l[i+1]='1'
        l[i]='0'
        
        break    
    else :
        
        i=i+1

l.reverse()
print(l)
s="".join(l)
result=int(s,2)
print(result)

int count1s(int num)
{
	char pat[16]={0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4};
	int cnt=0;
	char t= num&0xf;
	cnt=cnt+pat[t];
	t=(num&0xf0)>>4;
	cnt=cnt+pat[t];
	t=(num&0xf00)>>8;
	cnt=cnt+pat[t];
	t=(num&0xf000)>>12;
	cnt=cnt+pat[t];
	t=(num&0xf0000)>>16;
	cnt=cnt+pat[t];
	t=(num&0xf00000)>>20;
	cnt=cnt+pat[t];
	t=(num&0xf000000)>>24;
	cnt=cnt+pat[t];
	t=(num&0xf0000000)>>28;
	cnt=cnt+pat[t];
	return cnt;
}

#include <conio.h>
#include<stdio.h>
int findone(int temp);
int main( )
      {
	  int n,l,lnext;
	  printf("enter the number");
	  scanf("%d",&n);
	  l=findone(n);
	  printf("No of 1's in given number are %d",l);
      lnext=findone(++n);
      while(l!=lnext)
      {
                      lnext=findone(++n);
      }
        printf("\nthe next number is %d",n);             
	getch();
        return 0;
       }


int findone(int temp)
{
    int len=0,bin;
    while(temp!=0)
    {
                  bin=temp%2;
                  temp=temp/2;
                  if(bin==1)
                  {
                            len++;
                  }
    }
 return len;
}