Saturday, March 25, 2017

Check no duplicates in a char array


E.g.row = 5 col = 4. To check if the 5th bit is ‘1’. Set the other bits to zero.
int mask = 1 << col;
if (set[row] & mask != 0) return true;
Else set the 5th bit to ‘1’. set[row] = set[row] |  mask;
bits[4]    0000 0000 0000 0000 0000 0000 0000 0000
mask     0000 0000 0000 0000 0000 0000 0001 0000

public boolean checkUnique(char[] array) {
if (array == null) return true; //Or throw IllegalArgumentException
int[] set = new int[8]; //All together 8 * 32 positions
for (char c : array) {
int row = c / 32;  //integer access
int col = c % 32; //bit access
int mask = 1 << col;
if (set[row] & mask != 0) return false;
set[row] = set[row] | mask;
}
return true;
}

public boolean checkUnique(char[] array) {
try {
if (array == null) throw new IllegalArgumentException();
int[] set = new int[8]; //All together 8 * 32 positions
for (char c : array) {
int row = c / 32;  //integer access
int col = c % 32; //bit access
int mask = 1 << col;
if (set[row] & mask != 0) return false;
set[row] = set[row] | mask;
}
return true;
} catch (IllegalArgumentException e) {
System.out.println(“Input array is null.”);
}
}



No comments:

Post a Comment