How to increment bits correctly in an array?

Question

If I have a binary notation such as "1000010" which equals 66 and I want to increment it by one to "1000011" which equals 67. How is that done correctly in my array? Currently it's printing out "0100010" which is 34, but no where near the correct answer. I don't think my array is shifting correctly, nor will it increase size as the numbers get larger. Although, I can't make any assumptions about how big the array can be other than what's explicitly stated.

public class math {


//=================================================================
  // increment(A) returns an array of bits representing A+1.
  //=================================================================

  public static byte[] increment(byte[] A)
  {
    byte carry= 1;
    for(int i = 0; i<A.length; i++){
        byte b = A[i];
        A [i] ^= carry;
         carry &= b;
    }
    return A;
  }

  private static String toBinString (byte [] a) 
  {
      String res = "";
      for (int i = 0; i <a. length; i++) 
      {
          res = (a [i] == 0 ? "0": "1") + res;
      }
      return res;
}


/**
 * @param args
 */
public static void main(String[] args) {
         byte [] A ={1,0,0,0,0,1,0};

         increment(A);
             System.out.println (toBinString (A));


}
 }

related: http://stackoverflow.com/questions/1034473/java-iterate-bits-in-byte-array — , Sep 07 '11 at 00:25
In your declaration of A it looks like you want the leftmost (first) array be the most significant bit, in the rest of your program you consider the first element of the array as the least significant bit. Easiest solution would probably be to enter your number in reverse order in the array, or inverse the array... — fvu, Sep 07 '11 at 00:27
This solution worked for me: https://stackoverflow.com/questions/4421400/how-to-get-0-padded-binary-representation-of-an-integer-in-java — HoldOffHunger, Jun 07 '17 at 00:29

score 5 · Answer 1 · answered Aug 16 '12 at 14:42

5

The lazy (and secure) way for increment by one :

    String s = "1000010";
    for (int i = 0; i < 5; i++) {
        System.out.print(s);
        System.out.println("\t" + Integer.valueOf(s, 2));
        s = Integer.toBinaryString(Integer.valueOf(s, 2) + 1);
    }

Output :

(Edited for presentation)

answered Aug 16 '12 at 14:42

cl-r

1,264
1
12
26

This will not produce uniform results with variable-length binary numbers. I.E., 1 comes out as "1", 2 comes out as "10", 4 comes out as "100", etc.. It only works because of the specific numbers you're demonstrating here. – HoldOffHunger Jun 07 '17 at 00:28

Snowy Coder Girl · Answer 2 · 2011-09-07T01:44:10.477

This worked for me:

public static void main(String[] args) {
    byte [] A ={1,0,0,0,0,1,0};
    increment(A);
    System.out.println (toBinString (A));
}

public static byte[] increment(byte[] A) {
    boolean carry = true;
    for (int i = (A.length - 1); i >= 0; i--) {
        if (carry) {
            if (A[i] == 0) {
                A[i] = 1;
                carry = false;
            }
            else {
                A[i] = 0;
                carry = true;
            }
        }
    }

    return A;
}

private static String toBinString (byte [] a) {
      String res = "";
      for (int i = 0; i < a. length; i++) {
          res += (a [i] == 0 ? "0": "1") ;
      }
      return res;
}

score 1 · Answer 3 · answered Mar 12 '14 at 15:45

1

//Function call
incrementCtr(ctr, ctr.length - 1);

//Increments the last byte of the array
private static void incrementCtr(byte[] ctr, int index) {       

    ctr[index]++;

    //If byte = 0, it means I have a carry so I'll call 
    //function again with previous index
    if(ctr[index] == 0) {
        if(index != 0)
            incrementCtr(ctr, index - 1);
        else
            return;
    }
}

answered Mar 12 '14 at 15:45

gssln

11
1

what happens when you have a byte 0xFF? Looks like our code won't work for such a case – Jan Moritz Mar 07 '16 at 19:59

score 1 · Answer 4 · answered Oct 18 '16 at 11:29

1

Late but concise:

public static void increment(byte[] a) {
    for (int i = a.length - 1; i >= 0; --i) {
        if (++a[i] != 0) {
            return a;
        }
    }
    throw new IllegalStateException("Counter overflow");
}

answered Oct 18 '16 at 11:29

Christof R

863
6
10

score 0 · Answer 5 · answered Aug 16 '12 at 14:17

public static byte[] increment(byte[] array) {
    byte[] r = array.clone();
    for ( int i = array.length - 1; i >= 0; i-- ) {
        byte x = array[ i ];
        if ( x == -1 )
            continue;
        r[ i ] = (byte) (x + 1);
        Arrays.fill( r, i + 1, array.length, (byte) 0 );
        return r;
    }
    throw new IllegalArgumentException( Arrays.toString( array ) );
}

exception if overflow

score 0 · Answer 6 · answered Oct 29 '18 at 09:29

0

In this case you can iterate on all values.

public boolean increment() {
    int i = this.byteArray.length;

    while (i-->0 && ++this.byteArray[i]==0);

    return i != -1;
}

At the end you can increase the array's size.

answered Oct 29 '18 at 09:29

C Würtz

856
9
20

Les Hazlewood · Answer 7 · 2021-09-15T19:33:08.350

There are many solutions on this page that represent a native Java byte as a full array of numeric one and zero values. In other words, a single single byte (with 8 bits) is represented as an entire array of 8 individual numeric values (where each index in the array is a byte itself that represents the 1 or 0 value of each bit position).

That means for a given input byte (8 bits), an 8 byte array (64 bits) is used to represent ones and zeros. Consequently, an input byte array of length 4 (e.g. representing an int or unsigned int), would require 32 bytes (256 bits), and an input byte array of length 8 (e.g. for a long) would require 64 bytes (512 bits), and so on.

Thats exponential (O(n^c)) complexity - a relatively massive memory/performance expense to do something that the language already supports natively and efficiently. And if there are more than one of these byte array values to work with, that compounds the performance hit further.

The following is a correct (and working) solution if you have a standard byte array representing a single contiguous big-endian bit string and you want to increment it by one bit. It is nearly identical to Cristof R's solution, except that particular solution does not compile.

The following solution is most efficient if you don't need to create a copy of the input byte array, and is useful as an equivalent for iterator incrementation, e.g. i = i + 1 scenarios:

/**
 * Treats the specified byte array as a single contiguous big-endian 
 * bit string, and increments it by a single bit.  Does not throw an
 * exception on overflow and instead 'rolls' over to zero.
 */
public static void increment(byte[] a) {
    for (int i = a.length - 1; i >= 0; --i) {
        if (++a[i] != 0) {
            break;
        }
    }
}

If you don't want to modify the source bit string, you can just clone it before incrementing:

byte[] original = new byte[]{0, 0, 0, 0}; //integer value 0
byte[] copy = original.clone();
increment(copy);

Here's a little test program demonstrating:

public class IncrementBitExample {
    
    /**
     * Treats the specified byte array as a single contiguous big-endian
     * bit string, and increments it by a single bit.  Does not throw an
     * exception on overflow and instead 'rolls' over to zero.
     */
    public static void increment(byte[] a) {
        for (int i = a.length - 1; i >= 0; --i) {
            if (++a[i] != 0) {
                break;
            }
        }
    }

    public static String toBinary(byte b) {
        String bString = Integer.toBinaryString(b & 0xFF);
        return String.format("%8s", bString).replace(' ', '0');
    }

    public static String toBinary(byte[] bytes) {
        StringBuilder sb = new StringBuilder(16);
        for(byte b : bytes) {
            if (sb.length() > 0) {
                sb.append(' '); //separate byte segments for readability
            }
            String val = toBinary(b);
            sb.append(val);
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        byte[] b = new byte[]{0, 0, 0, 0}; // integer 0
        for(int i = 0; i <= 256; i++) {
            System.out.println("b: " + toBinary(b));
            increment(b); // effectively b = b + 1;
        }
    }
}

Running main shows the following output (snipped for brevity):

b: 00000000 00000000 00000000 00000000
b: 00000000 00000000 00000000 00000001
b: 00000000 00000000 00000000 00000010
b: 00000000 00000000 00000000 00000011
b: 00000000 00000000 00000000 00000100
b: 00000000 00000000 00000000 00000101
b: 00000000 00000000 00000000 00000110
b: 00000000 00000000 00000000 00000111
b: 00000000 00000000 00000000 00001000
b: 00000000 00000000 00000000 00001001
b: 00000000 00000000 00000000 00001010
b: 00000000 00000000 00000000 00001011
b: 00000000 00000000 00000000 00001100
b: 00000000 00000000 00000000 00001101
b: 00000000 00000000 00000000 00001110
b: 00000000 00000000 00000000 00001111
b: 00000000 00000000 00000000 00010000

... continued ...

b: 00000000 00000000 00000000 11111110
b: 00000000 00000000 00000000 11111111
b: 00000000 00000000 00000001 00000000

Notice the very last printed bit string. The loop iterator max value is 256 and that number cannot be represented as a single unsigned byte - it requires at least two bytes to represent. As a result, the incrementing of the 2nd-to-last bit string value of:

00000000 00000000 00000000 11111111 (integer value 255)

has to 'overflow' to the next byte to the left (big-endian), and produces the final value:

00000000 00000000 00000001 00000000 (integer value 256)

How to increment bits correctly in an array?

7 Answers7