CareerCup

Decimal can convert into base by divide and collecting the remainders,


For example:


Binary value of decimal 12


12 / 2 = 6 with remainder 0


6 / 2 = 3 with remainder 0


3/ 2 = 1 with remainder 1


1 / 2 = 0 with remainder 1

So the Binary value is 1100


Same formula can be applied to find Negative Base, but remember remainders have to be positive.


Like the sample found in wiki



Note, here -5/-3 = 2 with remainder 1 ,


If a/b = c with remainder d then bc + d = a , thus the c can be found like c = (a-d) / b


Let’s try to write Java method to calculate this.

private static void convertBase(int decimalVal,int base){



            StringBuffer buffer = new StringBuffer();


            while (decimalVal != 0){


                  int remainder = Math.abs((decimalVal % base)); //find positive remainder


                  decimalVal = (decimalVal - remainder) / base; // c = (a-d) / b


                  buffer.insert(0, remainder);


            }


            System.out.println(buffer);


}

convertBase(7,-2) = 11011

convertBase(6,-2) = 11010

convertBase(7,2) = 111

convertBase(6,2) = 110

private static void convertBase(int decimalVal,int base){
		if(base > 0 && decimalVal < 0){
			System.out.println("not possible");
			return;
		}	
        StringBuffer buffer = new StringBuffer();
        while (decimalVal != 0){
      
        	 int result = decimalVal / base;
        	 int remainder = decimalVal % base;
        	 if(remainder < 0){
        		 result++;
        		 remainder = decimalVal - base * result;
        	 }
        	 decimalVal = result;
             buffer.insert(0, remainder);
        }
        System.out.println(buffer);
	}

If we simulate 2-3 digits we can see the pattern of generated numbers. The code follows from observing how the range of positive/negative numbers changes. Time O( log n ).

long convert(long n)
{
	if(n == 0 || n == 1)
		return n;
		
	long res = 0, low, high, range;
	long digits = required_digits(n, low, high, range);	
	
	while(digits--)
	{
		res <<= 1;
		
		if(digits&1)
		{
			if( low <= n && n < low + range)
			{
				res |= 1;
				n += range;
			}
			low += range;						
		}
		else
		{
			if( high >= n && n > high - range)
			{
				res |= 1;
				n -= range;
			}
			high -= range;
		}		
		range>>=1;
	}
	
	return res;
}

long required_digits(long n, long& low, long& high, long& range)
{
	long digit = 1;	
	range = 1, low = 0, high = 1;
	
	while( low > n || n > high ) 
	{
		digit++;
		range <<= 1;
			
		if(digit&1)					
			high += range;					
		else		
			low -= range;				
	}
	
	return digit;
}

See Negative_base on wikipedia

Algorithm is same as positive-base conversion(e.g. base 2) but if you get remainder as -ve, you need to add the mod of base(e.g. | -2 | = 2) to remainder to get it to become non-negative and also add 1 to the remaining value after division by base.

public String convert(int number){
StringBuffer str = new StringBuffer();
while(number!=0){
int remainder = number/(-2);
int mod = number%(-2);
if(mod==-1){
remainder+=1;
mod=1;
}
str.insert(0, mod);
number=remainder;
}
return str.toString();
}

Compilable and running code:

// How to represent a number in base -2? (negative -2 base) eg 6 can be 11010 i.e. 16 -8 +0 -2 +0 = 6.
// When the num is +ve then we divide by (0-base) (here base if negative so 0-base is +ve) and save remainter by dividing num by (0-base) and after division num becomes 0-num
// when the num is -ve then we divide (0-(num+base)) by (0-base) and save remainder by dividing (0-(num+base)) by (0-base) and after division we put back sign for both num and base
// how remainder is saved:

#include <stdio.h>

int convertToNegativeBase(int num, int base, int *digits)
{
	int i=0;
	
	while(num != 0)
	{
		
		if(num > 0)
		{
			base = 0-base;
			digits[i++] = num%base;	
			num = num/base;
			num = 0-num;
		}
		else
		{
			num = 0-(num+base);
			base = 0-base;
			digits[i++] = num%base;
			num = num/base;
		}
		base = 0-base;
	}
	return i;
}

int main()
{
	int digits[100];
	int i = 0;
	int n = convertToNegativeBase(16,-2,digits);

	while(n > 0)
	{
		printf("%d",digits[--n]);
	}
}

int base_convert(int num, int base)
{
    int rem =   0;
    int idx = 0;
    int baseX   =   0;

    while( num )
    {
        rem =   num%10;
        baseX   +=   rem * pow(base,idx);
        idx++;
        num   /=  10;
    }

    return baseX;
}

Suppose you have a binary number 1101110. If we consider this as base -2, the difference is that the odd digits now represent a negative value. We simply need to convert the odd digits into base -2. Examples:

10=2^1 in binary and 110=2^2-2^1=2^1 in base -2
1000=2^3 in binary and 1100=2^4-2^3=2^3 in base -2

In general

2^n=2^{n+1}-2^n

and when n is odd, 2^{n+1} is even, hence positive in base -2. This allows us to rewrite an odd digit of a binary number ...0001000.... as ...0011000...

Therefore, to find the base -2 expansion of n, a simple solution to the problem would be:
1) Sum the odd powers of 2 until you obtain a number x > n.
2) Compute the `bit-wise and`

y = n & x

(as in C or C++)
3) Multiply y by 2 (aka bit-wise shift left) and then add to n:

z = (y << 1) + n

The binary expansion of z is the base -2 expansion of n.

String neg2base(int x){
	String ret = "";
	int remains = 0;
	while(Math.abs(x) != 0){
		remains = x%2 == 0?0:1;
		x -= remains;
		x /= -2;
		ret = remains + ret;
	}
	return remains + ret;
}

What a headache, but I managed it. It returns an integer where it's bits correspond to the base -2 encoding, it does it in O(log(n)) where n is the position of the highes bit:

import math

def convert(x):
    res = 0
    while True:
        sign = 1 if x >= 0 else -1
        p = math.floor(math.log2(abs(x)))
        if 2**p < abs(x):
            p += 1
        if (p % 2 == 0 and sign < 0) or (p % 2 == 1 and sign > 0):
            res += 2**(p+1)
        x = -(sign*(2**p) - x)
        res += 2**p
        if x == 0:
            break
    return res

don't you just take the two's complement of the base2 representation? i.e. 00101 (6 in base 2) --> 11010 (6 in base -2)