CODEWITHSUNDEEP
javaalgorithm
ridersingh92
ridersingh92

Reputation: 63

Forming a pattern of bits from a integer

I need help to design java code for generating bit array for any given integer in following manner:

23 should produce output as 1101011 (min length array) explaination :

positions are given as 1 -2 4 -8 16 -32 ....

So 1101011 can be evaluated as:

1*1 + 1*-2 + 0*4+ 1*-8 + 0*16 +1*-32 + 1*64 = 23

Upvotes: 5

Views: 121

Answers (2)

YK S
YK S

Reputation: 3430

Since it is not usual int to binary conversion, at each step we need to consider two cases as at each position there can be only two choices 0 or 1. This is done recursively in the below program:

public class ModifiedIntToBinaryConversion{

    public static int calcBinaryString(int reqSum, int currSum, int add, String bs) {

        if (reqSum == currSum) {     // base condtion 1
            System.out.println("The string is \n" + bs);
            return currSum;
        }

        if (add + currSum > reqSum) {   // base condtion 2
            return 0;
        }

        int newAdd = add * -2;

        // System.out.println("new add is "+ newAdd +" currSum is "+ currSum);
        int s1 = calcBinaryString(reqSum, currSum + add, newAdd, bs + "1");

        if (s1 == reqSum)
            return s1;

        int s2 = calcBinaryString(reqSum, currSum, newAdd, bs + "0");
        return s2;
    }

    public static void calcBinaryString(int sum) {
        int s1 = calcBinaryString(sum, 0, 1, "");
        if(s1 != sum) {
            System.out.println("The binary equivalent couldn't be found");
        }
    }

    public static void main(String[] args) {
        calcBinaryString(23);
    }
}

Now base condition 1 is clear as I am just checking whether required sum and calculated sum are equal.

For base condition 2, I will accept it's result of debugging and a bit of thought as I was getting Stackoverflow errors. Once the calculated sum becomes greater than the required sum and then we take the next -ve number so that it become less than req. sum. But then the next +ve number will be greater than the -ve number we just considered and thus the chances are very less that the calculated sum will ever be equal to req. sum.

Upvotes: 1

rplantiko
rplantiko

Reputation: 2738

This is the so-called negabinary representation of numbers (described first by Vittorio Grünwald in 1885). They can be encoded in a fashion very similar to the usual binary representation, just working with -2 instead of 2 as base (Java code inspired by C# code on https://en.wikipedia.org/wiki/Negative_base ):

class EncodeNegaBinary {

  public static void main(String[] args) {

    int n=0,input=0;
    String result="";
    final String[] BITS = { "0","1" };

    if (args.length != 1) {
      System.err.println("Please enter an integer to be converted");
      return;
    } else {
      input = n = Integer.parseInt(args[0]);
    }

    while (n != 0) {
      int r = n%-2;
      n /= -2;
      if (r == -1) {
        r=1;
        n++;
      }
      result = BITS[r] + result;
    }

    System.out.printf( "%d -> %s\n", input, result);

  }
}

Upvotes: 5

Related Questions