multiplying number in binary by two

Question

I am trying to multiply a binary number by 2, without coveting to other counting system.

my algorithm is:

• if lead digi is 1, make 0 and append 1 to leading ('1'00 -> 1'0'00) digit in marks for example
• from back of array, if (i-th element is 1, make it in to 0), then
• hunt for next 0
• make the 0, into a 1
• make the between elements which are surely 1s, all into 0s

• termination point is most likely wrong, I can easy fix via flag (on step 1), and if statement, to determine end of loop(step 2) variable

  String ori = "10001";
  
  char[] arry = ori.toCharArray();
  
  System.out.println("start: " + new String(arry));
  
  if (arry[0] == '1') {
      arry = ("1" + ori).toCharArray();
      arry[1] = '0';
  }
  
  System.out.println("start: " + new String(arry));
  
  for (int i = arry.length - 1; i > 0; i--) { // not the lend digi
  
      if (isOneThenChange(arry, i)) {
  
          // hunt down next 0
          int index = hunt(arry, i);
  
          if (index == -1) {
  
              for (int ii = 0; ii < arry.length; ii++) {
  
                  System.out.print(arry[ii]);
              }
  
              System.exit(0);
          }
  
          System.out.println("index is: " + index);
          System.out.println("01234564");
          System.out.println(arry);
  
          // make it into 1
          arry[index] = '1';
  
          // make the 1s in between 0s..
          //// safe assumption index.. i and all 1s
          for (int k = index - 1; k < i; k++) {
              arry[k] = '1';
          }
      }
  
      // Continue the loop and look for the next one
  } 
  
  System.out.println("end:   " + new String(arry));
  

Method to hunt down 0:

private static int hunt(char[] arry, int i) {

    for (int j = i; j > 0; j--) {
        if (arry[j] == '0')
            return j;
    }
    return -1;
}

Method that flips bits from 1 to 0:

private static boolean isOneThenChange(char[] a, int i) {
    if (a[i] == '1') {
        a[i] = '0';
        return true;
    }
    return false;
}

}

I have been unsuccessful in debugging my code, i suspect it to be in step 3,4,5

How do i debug my algorithm, and get it to function as intended?

Answer 1

In binary, if you shift left, you are multiplying by 2. So, in terms of strings, if you append a 0, you are effectively multiplying by 2.

x = 1110   // 14 in decimal

x << 1     // 28 in decimal

But, since you are using strings:

String x = "1110"; // 14 in decimal

// As long as x != 0, append "0"
if (!x.equals("0")) {

  x = x + "0"; // 11100 = 28
}         

It's the same as shifting left on a base-10 number multiplies by 10:

12
120
1,200

For any base (radix) one shift to the left multiplies your number by the base. (in this case base 2). And shifting to the right effectively divides the number by the base the number and rounds down.