CareerCup

Exchange the lowest order adjacent 1 and 0.

def nearest(num):
    p = 1
    while num & p == 0:
        p <<= 1
    if p == 1:
        while num & p != 0:
            p <<= 1
    return num ^ (p | p >> 1)

Hi Mehrdad, that is certainly true and it looks good. What remains now is to minimize |x-y|. Sorry I edited the task right after I posted it, I forgot to write the minimization condition.

I like the trick with two's complement (x & -x), awesome :)

Exchange the lowest order 1 and 0.

def nearest(num):
    p = 1
    while num & p == 0:
        p <<= 1
    if p == 1:
        while num & p != 0:
            p <<= 1
    return num ^ (p | p >> 1)

find the next smaller and next greater number with same set of bits.
Find the one with minimum difference and return the same.

finding next greater -
1) find the first one from right;
2) find the first zero from right and first one.
3) set the first zero as One and right next to it as Zero.
4) Set all remaining zeros first and then Ones.

Same for other also...

if bit 0 is set, find the first unset bit, then set it and unset the bit to its right.
Otherwise (bit 0 is not set), find first set bit, unset it and set the bit to its right.

Suppose x has 5 bit set. Return y such that it same high bit as x except the lower one bit.

example
x (bitwise) = 11110100
then y = 11110010

border cases when the first bit is set, in this case choose the one higher bit.

Suppose x has 5 bit set, choose y such that it has same exact 4 high bit set, except the smallest 1 bit. This can be one position to the right or left.

Example :
x (bitwise) : 11110100
y (bitwise) : 11110010

public int findMinDistanceNumber(int number) throws Exception {
		int powOf2 = 1;
		if (number <= 0 || number >= Integer.MAX_VALUE - 2) throw new Exception("Invalid number!");
		//Find the 0 before/after the first 1 and toggle
		while(powOf2 < Integer.MAX_VALUE - 2) {
			// If power of 2 bit is set
			if ((number & powOf2) > 0) {
				// Check right first if that bit can be set to 1
				if (powOf2 != 1 && (number & (powOf2 >> 1))==0) {
					number = number + (powOf2 >> 1) - powOf2;
					break;
				}
				// Else check left
				if ((number & (powOf2 << 1))==0) {
					number = number + (powOf2 << 1) - powOf2;
					break;
				}
			} 
			powOf2 = powOf2 << 1;
		}
		return number;
}

def solve(input: Long): Long = {
    def calculateMask(num: Long, mask: Int): Int = {
      val shifted = num >> 1
      if ((shifted & 1) != (num & 1))
        mask
      else
        calculateMask(shifted, mask << 1)
    }
    
    if (input < 1 || input > Math.pow(2, 32).toLong - 2)
      throw new IllegalArgumentException
    
    //Exchange the lowest order adjacent 1 and 0
    input ^ calculateMask(input, 3)
  }

1. get the bit count for X
n = get_bit_count(X);
2. get the one count for X
one_cnt = get_one_count(X)

int min = INT_MAX;

for(i = 1;i < 2 ^ n; i++ ) {
if(one_cnt = = get_one_count(i) &&
X != i) {
if(i < min)
min = i;
}
}
return min

unsigned int func(unsigned int x)
{
	int i=0;
	
	while (  !(  ((x & 1<<i) ? 1:0)  ^  ((x & 1<<(i+1)) ? 1:0)  ) )
		i++;
	
	return x ^ 3<<i;
}

Find "01" or "10" within the binary representation of number and swap it to "10" or "01" respectively. This will give a number with same set bits and minimum difference from x.

var x = parseInt("01010111",2);

function first(n){
  return n & ~(n-1);
}

function flip(x,n){
  var tmp = n + (n>>1);
  return tmp^x;
}

var f0 = first(~x);

var result = flip(x, (f0>1)?f0:first(x));

unsigned int minDiffBitSwap(unsigned int x) {
	unsigned int y = x;
	if (x & 1) {
		for (int i = 1; i < 32; ++i) {
			int mask = (1 << i);
			if (!(x & mask)) {
				y |= mask;
				mask >>= 1;
				y ^= mask;
			}
		}
	} else {
		for (int i = 1; i < 32; ++i) {
			int mask = (1 << i);
			if (x & mask) {
				y ^= mask;
				mask >>= 1;
				y |= mask;
			}
		}
	}
	return y;
}

/*
Strategy: From LSB to MSB, identify first consecutive bits
those are different and swap/flip them.
No solution for 0x0 and 0xffffffffffffffff
*/
#include <iostream>
#include <stdio.h>

using namespace std;

int main(){
    unsigned long long x;
    scanf("%lld", &x);
    
    if(x == 0 || x == 0xffffffffffffffff) {
        cout << "No solution\n";
        return 0;
    }
    
    unsigned long long x_tmp = x;
    int i=0;
    int prevBit = x_tmp & 0x1;
    while(x_tmp){
        x_tmp >>= 1;
        if(prevBit != (x_tmp&0x1)) break;
        prevBit = x_tmp & 0x1;
        i++;
    }
    
    unsigned long long y = x ^ (3<<i);
    cout << y << endl;
    
    return 0;
}

// The idea is to start from the LMB by taking a pair of consecutive bits.
// If the consecutive bits are not equal, they are exchanged. The resulting number after
// exchange is the result.
// If the bits either all 0s or 1s, it is not applicable as all the bits are same.
// Otherwise there should be atleast a pair of consecutive bits which are not same - 01 or 10
// We don't cosider if the pair of bits are at the righmost position, as after exchanging the bits
// one of the numbers will have a leading zero which doesn't get counted as part of the unsigned number.
// Example - 
// 10000                      : bitset = 1 1s, 4 0s                
// 01000    =>  1000    : bitset =  1 1s, 3 0s


// flipBit flips the bit at position pos
func flipBit(n uint32, pos uint) uint32 {
	mask := uint32(1) << pos
	n = n ^ mask
        return n
}

// nearestBitset returns a number m with same bitset as n such that |n - m| is minimimum.
// It returns n if it is not applicable
func nearestBitset(n uint32) uint32 {
	// bit positions
	pos1, pos2 := uint(0), uint(1)
	mask := uint32(1)
	// how far should pos2 go
	m := n >> mask
	for m > uint32(0x11) {
		if ((n >> pos1) & mask) != ((n >> pos2) & mask) {
			fmt.Printf("exchanging bits at positions: %d, %d\n", pos1, pos2)
			n = toggleBit(n, pos1)
			n = toggleBit(n, pos2)
			return n
		}
		pos1++
		pos2++
		m >>= mask
	}
	return n
}

if(x&1){
		y = x << 1;
	}
	else{
		y = x >> 1;
	}

For example, we reversing one bit 1 to 0, so we have to revers another bit from 0 to 1 to have same bits set.
We can repeat such pair operations several times to get any y with same bits set as x.
Consider y > x, lets find nearest (min) y. Each bit corresponds to order of 2.
Consider y has reversed bits on position K and N (K>N, N=K+I), in this case y-x = 2orderK-2orderN=2OrderK*(2orderI-1)
We can see that min of y-x will be in case I=1 -> K and N are nearest bits and in this case y-x=2orderK.
Also K should be minimum to get minimum y-x. In this case x^y=2orderK*(2+1) =3*2orderK . We need to find K.
Same logic for case x>y, depends of is x odd or not.

public static int getNearestSameBitSet(int x)
   {
       if(x==0||x==Integer.MAX_VALUE)  {
         return -1;       
       }

       int y;

       if(x%2!=0)   //starts from 1 on the right side
       {
           int i = 1;

           while (i<Integer.MAX_VALUE)
           {
               y=x+i;
               if((x^y)==(3*i)) return y;
               i <<= 1;
           }
       } else if((x%2)==0)   //starts from 0 on the right side
       {
           int i = 1;
           while (i<x)
           {
               y=x-i;
               if((x^y)==(3*i)) return y;
               i <<= 1;
           }
       }

       return -1;
   }

unsigned int func(unsigned int x)
{
    if(x==0)
        return 1;

    int i=0;
    for(i=0 ; i<31 ; i++)
    {
        if( ((x&1<<i) > 0 && (x&1<<i+1) > 0) || ((x&1<<i) == 0 && (x&1<<i+1) == 0) )
            continue;
        else
            break;
    }

    x = x^(1<<i);
    x = x^(1<<i+1);

    return x;
}

unsigned int func(unsigned int x)
{
    if(x==0)
        return 1;

    int i=0;
    for(i=0 ; i<31 ; i++)
    {
        if( ((x&1<<i) > 0 && (x&1<<i+1) > 0) || ((x&1<<i) == 0 && (x&1<<i+1) == 0) )
            continue;
        else
            break;
    }

    x = x^(1<<i);
    x = x^(1<<i+1);

    return x;
}

Exchange lowest neighboring 1 and 0.

#include <functional> 
#include <iostream> 
#include <algorithm> 
#include <sstream> 
#include <string> 
#include <utility> 
#include <vector> 
#include <cmath> 
#include <queue> 
#include <map> 
#include <set>

using namespace std;

int bit_count(int n)
{
    int r=0;
    while(n)
    {
        r++;
        n &= (n-1);
    }

    return r;
}


int similar_etalon(int n)
{
    int bits = bit_count(n);

    int smaller = -1;
    int greater = -1;

    for(int i = n-1; i >= 0; --i)
    {
        if (bit_count(i) == bits)
        {
            smaller = i;
            break;
        }
    }


    for(int i = n+1; ; ++i)
    {
        if (bit_count(i) == bits)
        {
            greater = i;
            break;
        }
    }

    if (smaller == -1)
        return greater;

    if (n-smaller < greater-n)
        return smaller;

    return greater;
}


int similar(int n)
{
    if (n == 0)
        throw 0;


    int last_bit = n ^ (n & (n-1));

    if (last_bit > 1)
    {
        int result = n - last_bit + (last_bit >> 1);

        return result;
    }
    else
    {
        int k = n + 1;
        int last_zero = k ^ (k & (k-1));

        int result = n + last_zero - (last_zero >> 1); 

        return result;
    }
}


int main()
{
    int total = 0;
    int passed = 0;
    for(int i = 1; i <= (1 << 16); ++i, ++total)
    {
        int e = similar_etalon(i);
        int r = similar(i);

        if (e != r)
        {
            cout << "Test Case #" << i << " FAILED! " << "Expected: " << e << " Received: " << r << endl;
        }
        else
        {
            passed++;
        }
    }


    cout << "Passed " << passed << "/" << total << endl;

}

Exchange lowest neighbouring 1 and 0.

#include <functional> 
#include <iostream> 
#include <algorithm> 
#include <sstream> 
#include <string> 
#include <utility> 
#include <vector> 
#include <cmath> 
#include <queue> 
#include <map> 
#include <set>

using namespace std;

int bit_count(int n)
{
    int r=0;
    while(n)
    {
        r++;
        n &= (n-1);
    }

    return r;
}


int similar_etalon(int n)
{
    int bits = bit_count(n);

    int smaller = -1;
    int greater = -1;

    for(int i = n-1; i >= 0; --i)
    {
        if (bit_count(i) == bits)
        {
            smaller = i;
            break;
        }
    }


    for(int i = n+1; ; ++i)
    {
        if (bit_count(i) == bits)
        {
            greater = i;
            break;
        }
    }

    if (smaller == -1)
        return greater;

    if (n-smaller < greater-n)
        return smaller;

    return greater;
}


int similar(int n)
{
    if (n == 0)
        throw 0;


    int last_bit = n ^ (n & (n-1));

    if (last_bit > 1)
    {
        int result = n - last_bit + (last_bit >> 1);

        return result;
    }
    else
    {
        int k = n + 1;
        int last_zero = k ^ (k & (k-1));

        int result = n + last_zero - (last_zero >> 1); 

        return result;
    }
}


int main()
{
    int total = 0;
    int passed = 0;
    for(int i = 1; i <= (1 << 16); ++i, ++total)
    {
        int e = similar_etalon(i);
        int r = similar(i);

        if (e != r)
        {
            cout << "Test Case #" << i << " FAILED! " << "Expected: " << e << " Received: " << r << endl;
        }
        else
        {
            passed++;
        }
    }


    cout << "Passed " << passed << "/" << total << endl;

}

All you need to do is to swap leftmost neighbouring 1 and 0. This can be done in constant time.

You need to find the first two bits with different value, 0 and 1, or 1 and 0, for that porpuose you need XOR, then toggle those bits using XOR again.

For example:

number = 11

Bit representation: 1011

Posible answers:

0111 = 7

1110 = 12

1101 = 13

All these numbers have the same amount of 1’s, but according to restriction, the answer is 1110 = 12.

Using toggle(int n) you will encounter than 1011 the LSB and third LSB are different, so just toggle those bits using XOR, and that is the answer.

int toggle (int n) {
    if (n == 0)
        return 0;
    int i = 0;
    while (true) {
        if ((n & 1) ^ ((n >> ++i) & 1))
        {
            n ^= 1 << 0;
            n ^= 1 << i;
            return n;
        }
    }
    return n;
}

I think this problem is the same as "find the next(previous) integer with the same number of bit set", code as follows:

unsigned int Next(unsigned int x) {
	// test: x = 01101110
	int a = x & ~(x - 1); // a = 00000010
	int b = x + a;		  // b = 01110000
	int c = x & ~b;		  // c = 00001110
	int d = c / a >> 1;   // d = 00000011

	return b | d; // ans = 01110011
}

unsigned int Previous(unsigned int x) {
	// test: x = 01110011
	unsigned int a = x & ~(x - 1);         // a = 00000001
	unsigned int b = x + a;                // b = 01110100
	unsigned int c = x & b;				   // c = 01110000
	unsigned int d = (c & ~(c - 1)) >> 1;  // d = 00001000
	unsigned int e = ~x & b;	           // e = 00000100
	unsigned int f = d / e;				   // f = 00000010
	unsigned int g = e - 1;		           // g = 00000011

	return (c & ~(d << 1)) | d | f * g;	// ans = 01101110
}


unsigned int solve(unsigned int x) {
	unsigned int pre = Previous(x);
	unsigned int next = Next(x);

	return x - pre < next - x ? pre : next;
}

def bit_change(x):
	return (x&1)*(x^(~x&(x+1))^((~x&(x+1))>>1))+(1-x&1)*(x^(x&(~x+1))^((x&(~x+1))>>1))

If the first (rightmost) bit is 0, set the first set bit to 0, and the bit to the right of it to 1. If the first bit is 1, then set the first unset bit to 1, and the bit to the right of it to 0.

If the LSB is 0 find the least significant set bit, unset it and add 1 to the result;
If the LSB is 1 find the least significant unset bit, set it and deduct 1 from the result;

public static int findClosestWithOneChange(int a) {
            if (a % 2 == 0) {
                int firstOne = a & -a;
                return a - firstOne + 1;
            } else {
                int b = a + 1;
                int firstZero = b & -b;
                return a + firstZero - 1;
            }
        }

int firstOne = (x & -x);
int i = log(firstOne)/log(2.0);

y = (x >> (i+1) ) | ( 1<<32);


first we need to find the first set bit of x (from right).let's say first 1 occurred at i-th bit. if we shift all bits of x, (i+1) times to the right, then x will have one set-bit less than before. now, if we change the last bit (32-th place) to 1, the result would have equal number of 1's and is different from x.



Update: When I wrote this solution, writers of question hadn't mentioned the constraint of minimizing |y-x|

Let's move all bits one position left, carry-over the first bit if it is set.

unsigned foo(unsigned x) {
    unsigned y = x >> 1;
    if (x & 1) {
        y |= 0x10000000; // 0b1000...000
    }
    return y;
}

Let's move all bits one position left, carry-over the first bit if it is set.

unsigned foo(unsigned x) {
    unsigned y = x >> 1;
    if (x & 1) {
        y |= 0x10000000; // 0b1000...000
    }
    return y;
}

Let's move all bits one position left, carry-over the first bit if it is set.

unsigned foo(unsigned x) {
unsigned y = x >> 1;
if (x & 1) {
y |= 0x10000000; // 0b1000...000
}
return y;
}

Let's move all bits one position left, carry-over the first bit if it is set.

unsigned foo(unsigned x) {
unsigned y = x >> 1;
if (x & 1) {
y |= 0x10000000; // 0b1000...000
}
return y;
}