I am confused about how a bit vector would work to do this (not too familiar with bit vectors). Here is the code given. Could someone please walk me through this?
public static boolean isUniqueChars(String str) {
int checker = 0;
for (int i = 0; i < str.length(); ++i) {
int val = str.charAt(i) - 'a';
if ((checker & (1 << val)) > 0) return false;
checker |= (1 << val);
}
return true;
}
Particularly, what is the checker doing?
int checker is used here as a storage for bits. Every bit in integer value can be treated as a flag, so eventually int is an array of bits (flag). Each bit in your code states whether the character with bit's index was found in string or not. You could use bit vector for the same reason instead of int. There are two differences between them:
Size. int has fixed size, usually 4 bytes which means 8*4=32 bits (flags). Bit vector usually can be of different size or you should specify the size in constructor.
API. With bit vectors you will have easier to read code, probably something like this:
vector.SetFlag(4, true); // set flag at index 4 as true
for int you will have lower-level bit logic code:
checker |= (1 << 5); // set flag at index 5 to true
Also probably int may be a little bit faster, because operations with bits are very low level and can be executed as-is by CPU. BitVector allows writing a little bit less cryptic code instead plus it can store more flags.
For future reference: bit vector is also known as bitSet or bitArray. Here are some links to this data structure for different languages/platforms:
I have a sneaking suspicion you got this code from the same book I'm reading...The code itself here isn't nearly as cryptic as the the operators- |=, &, and << which aren't normally used by us layman- the author didn't bother taking the extra time out in explaining the process nor what the actual mechanics involved here are. I was content with the previous answer on this thread in the beginning but only on an abstract level. I came back to it because I felt there needed to be a more concrete explanation- the lack of one always leaves me with an uneasy feeling.
This operator << is a left bitwise shifter it takes the binary representation of that number or operand and shifts it over however many places specified by the operand or number on the right like in decimal numbers only in binaries. We are multiplying by base 2-when we move up however many places not base 10- so the number on the right is the exponent and the number on the left is a base multiple of 2.
This operator |= take the operand on the left and or's it with the operand on the right- and this one -'&'and's the bits of both operands to left and right of it.
So what we have here is a hash table which is being stored in a 32 bit binary number every time the checker gets or'd ( checker |= (1 << val)) with the designated binary value of a letter its corresponding bit it is being set to true.
The character's value is and'd with the checker (checker & (1 << val)) > 0)- if it is greater than 0 we know we have a dupe- because two identical bits set to true and'd together will return true or '1''.
There are 26 binary places each of which corresponds to a lowercase letter-the author did say to assume the string only contains lowercase letters- and this is because we only have 6 more (in 32 bit integer) places left to consume- and than we get a collision
00000000000000000000000000000001 a 2^0
00000000000000000000000000000010 b 2^1
00000000000000000000000000000100 c 2^2
00000000000000000000000000001000 d 2^3
00000000000000000000000000010000 e 2^4
00000000000000000000000000100000 f 2^5
00000000000000000000000001000000 g 2^6
00000000000000000000000010000000 h 2^7
00000000000000000000000100000000 i 2^8
00000000000000000000001000000000 j 2^9
00000000000000000000010000000000 k 2^10
00000000000000000000100000000000 l 2^11
00000000000000000001000000000000 m 2^12
00000000000000000010000000000000 n 2^13
00000000000000000100000000000000 o 2^14
00000000000000001000000000000000 p 2^15
00000000000000010000000000000000 q 2^16
00000000000000100000000000000000 r 2^17
00000000000001000000000000000000 s 2^18
00000000000010000000000000000000 t 2^19
00000000000100000000000000000000 u 2^20
00000000001000000000000000000000 v 2^21
00000000010000000000000000000000 w 2^22
00000000100000000000000000000000 x 2^23
00000001000000000000000000000000 y 2^24
00000010000000000000000000000000 z 2^25
So, for an input string 'azya', as we move step by step
string 'a'
a =00000000000000000000000000000001
checker=00000000000000000000000000000000
checker='a' or checker;
// checker now becomes = 00000000000000000000000000000001
checker=00000000000000000000000000000001
a and checker=0 no dupes condition
string 'az'
checker=00000000000000000000000000000001
z =00000010000000000000000000000000
z and checker=0 no dupes
checker=z or checker;
// checker now becomes 00000010000000000000000000000001
string 'azy'
checker= 00000010000000000000000000000001
y = 00000001000000000000000000000000
checker and y=0 no dupes condition
checker= checker or y;
// checker now becomes = 00000011000000000000000000000001
string 'azya'
checker= 00000011000000000000000000000001
a = 00000000000000000000000000000001
a and checker=1 we have a dupe
Now, it declares a duplicate
I also assume that your example comes from the book Cracking The Code Interview and my answer is related to this context.
In order to use this algorithm to solve the problem, we have to admit that we only are going to pass characters from a to z (lowercase).
As there is only 26 letters and these are properly sorted in the encoding table we use, this guarantees us that all the potential differences str.charAt(i) - 'a' will be inferior to 32 (the size of the int variable checker).
As explained by Snowbear, we are about to use the checker variable as an array of bits. Lets have an approach by example :
Let's say
str equals "test"
checker == 0 (00000000000000000000000000000000)
In ASCII, val = str.charAt(i) - 'a' = 116 - 97 = 19
What about 1 << val ?
1 == 00000000000000000000000000000001
1 << 19 == 00000000000010000000000000000000
checker |= (1 << val) means checker = checker | (1 << val)
so checker = 00000000000000000000000000000000 | 00000000000010000000000000000000
checker == 524288 (00000000000010000000000000000000)
checker == 524288 (00000000000010000000000000000000)
val = 101 - 97 = 4
1 == 00000000000000000000000000000001
1 << 4 == 00000000000000000000000000010000
checker |= (1 << val)
so checker = 00000000000010000000000000000000 | 00000000000000000000000000010000
checker == 524304 (00000000000010000000000000010000)
and so on.. until we find an already set bit in checker for a specific character via the condition
(checker & (1 << val)) > 0
Hope it helps
I think all these answers do explain how this works, however i felt like giving my input on how i saw it better, by renaming some variables, adding some others and adding comments to it:
public static boolean isUniqueChars(String str) {
/*
checker is the bit array, it will have a 1 on the character index that
has appeared before and a 0 if the character has not appeared, you
can see this number initialized as 32 0 bits:
00000000 00000000 00000000 00000000
*/
int checker = 0;
//loop through each String character
for (int i = 0; i < str.length(); ++i) {
/*
a through z in ASCII are charactets numbered 97 through 122, 26 characters total
with this, you get a number between 0 and 25 to represent each character index
0 for 'a' and 25 for 'z'
renamed 'val' as 'characterIndex' to be more descriptive
*/
int characterIndex = str.charAt(i) - 'a'; //char 'a' would get 0 and char 'z' would get 26
/*
created a new variable to make things clearer 'singleBitOnPosition'
It is used to calculate a number that represents the bit value of having that
character index as a 1 and the rest as a 0, this is achieved
by getting the single digit 1 and shifting it to the left as many
times as the character index requires
e.g. character 'd'
00000000 00000000 00000000 00000001
Shift 3 spaces to the left (<<) because 'd' index is number 3
1 shift: 00000000 00000000 00000000 00000010
2 shift: 00000000 00000000 00000000 00000100
3 shift: 00000000 00000000 00000000 00001000
Therefore the number representing 'd' is
00000000 00000000 00000000 00001000
*/
int singleBitOnPosition = 1 << characterIndex;
/*
This peforms an AND between the checker, which is the bit array
containing everything that has been found before and the number
representing the bit that will be turned on for this particular
character. e.g.
if we have already seen 'a', 'b' and 'd', checker will have:
checker = 00000000 00000000 00000000 00001011
And if we see 'b' again:
'b' = 00000000 00000000 00000000 00000010
it will do the following:
00000000 00000000 00000000 00001011
& (AND)
00000000 00000000 00000000 00000010
-----------------------------------
00000000 00000000 00000000 00000010
Since this number is different than '0' it means that the character
was seen before, because on that character index we already have a
1 bit value
*/
if ((checker & singleBitOnPosition) > 0) {
return false;
}
/*
Remember that
checker |= singleBitOnPosition is the same as
checker = checker | singleBitOnPosition
Sometimes it is easier to see it expanded like that.
What this achieves is that it builds the checker to have the new
value it hasnt seen, by doing an OR between checker and the value
representing this character index as a 1. e.g.
If the character is 'f' and the checker has seen 'g' and 'a', the
following will happen
'f' = 00000000 00000000 00000000 00100000
checker(seen 'a' and 'g' so far) = 00000000 00000000 00000000 01000001
00000000 00000000 00000000 00100000
| (OR)
00000000 00000000 00000000 01000001
-----------------------------------
00000000 00000000 00000000 01100001
Therefore getting a new checker as 00000000 00000000 00000000 01100001
*/
checker |= singleBitOnPosition;
}
return true;
}
Reading Ivan's answer above really helped me, although I would phrase it somewhat differently.
The << in (1 << val) is a bit shifting operator. It takes 1 (which in binary is represented as 000000001, with as many preceding zeroes as you like / are allocated by memory) and shifts it to the left by val spaces. Since we're assuming a-z only and subtracting a each time, each letter will have a value of 0-25, which will be that letter's index from the right in the checker integer's boolean representation, since we will move the 1 to the left in checker val times.
At the end of each check, we see the |= operator. This merges two binary numbers, replacing all 0's with 1's if a 1 exists in either operand at that index. Here, that means that wherever a 1 exists in (1 << val), that 1 will be copied over into checker, while all of checker's existing 1's will be preserved.
As you can probably guess, a 1 functions here as a boolean flag for true. When we check to see if a character is already represented in the string, we compare checker, which at this point is essentially an array of boolean flags (1 values) at the indexes of characters that have already been represented, with what is essentially an array of boolean values with a 1 flag at the index of the current character.
The & operator accomplishes this check. Similar to the |=, the & operator will copy over a 1 only if both operands have a 1 at that index. So, essentially, only flags already present in checker that are also represented in (1 << val) will be copied over. In this case, that means only if the current character has already been represented will there be a 1 present anywhere in the result of checker & (1 << val). And if a 1 is present anywhere in the result of that operation, then the value of the returned boolean is > 0, and the method returns false.
This is, I'm guessing, why bit vectors are also called bit arrays. Because, even though they aren't of the array data type, they can be used similar to the way arrays are used in order to store boolean flags.
There are couple of excellent answers already provided above. So I don't want to repeat what's everything already said. But did want to add couple of things to help with the above program as I just worked through the same program and had couple of questions but after spending some time, I have more clarity on this program.
First of all "checker" is used to track the character which is already traversed in the String in order to see if there are any characters are getting repeated.
Now "checker" is an int data type so it can only have 32 bits or 4 bytes (depending upon platform) so this program can only work correctly for a character set within a range of 32 characters. That's the reason, this program subtracts 'a' from each character in order to make this program run for only lower case characters. However if you mix lower and upper case characters then it would not work.
By the way, if you do not subtract 'a' from each character (see below statement) then this program will work correctly for only String with upper case characters or String with only lower case characters. So the scope of above program increases from just lower case characters to upper case characters too but they can't be mixed together.
int val = str.charAt(i) - 'a';
However I wanted to write a generic program using Bitwise Operation which should work for any ASCII characters without worrying about upper case, lower case, numbers or any special character. In order to do this, our "checker" should be large enough to store 256 characters (ASCII Character Set size). But an int in Java would not work as it can only store 32 bits. Hence in below program, I am using BitSet class available in JDK which can have any user defined size passed while instantiating a BitSet object.
Here is a program which does the same thing as above program written using Bitwise operator but this program will work for a String with any character from ASCII character set.
public static boolean isUniqueStringUsingBitVectorClass(String s) {
final int ASCII_CHARACTER_SET_SIZE = 256;
final BitSet tracker = new BitSet(ASCII_CHARACTER_SET_SIZE);
// if more than 256 ASCII characters then there can't be unique characters
if(s.length() > 256) {
return false;
}
//this will be used to keep the location of each character in String
final BitSet charBitLocation = new BitSet(ASCII_CHARACTER_SET_SIZE);
for(int i = 0; i < s.length(); i++) {
int charVal = s.charAt(i);
charBitLocation.set(charVal); //set the char location in BitSet
//check if tracker has already bit set with the bit present in charBitLocation
if(tracker.intersects(charBitLocation)) {
return false;
}
//set the tracker with new bit from charBitLocation
tracker.or(charBitLocation);
charBitLocation.clear(); //clear charBitLocation to store bit for character in the next iteration of the loop
}
return true;
}
Simple Explanation (with JS code below)
32-bitDEC64 for JS.0th index if we find a in the string, 1st for b & so on.Summary of operations:
checker & index of the characterInt-32-Arraysif the output of the operation was 1output == 1
checker variable has that particular index-th bit set in both arraysoutput == 0
checker & index of the character1checkerAssumptions:
a is 97Given below is the JavaScript source code.
function checkIfUniqueChars (str) {
var checker = 0; // 32 or 64 bit integer variable
for (var i = 0; i< str.length; i++) {
var index = str[i].charCodeAt(0) - 96;
var bitRepresentationOfIndex = 1 << index;
if ( (checker & bitRepresentationOfIndex) > 1) {
console.log(str, false);
return false;
} else {
checker = (checker | bitRepresentationOfIndex);
}
}
console.log(str, true);
return true;
}
checkIfUniqueChars("abcdefghi"); // true
checkIfUniqueChars("aabcdefghi"); // false
checkIfUniqueChars("abbcdefghi"); // false
checkIfUniqueChars("abcdefghii"); // false
checkIfUniqueChars("abcdefghii"); // false
Note that in JS, despite integers being of 64 bits, a bit wise operation is always done on 32 bits.
Example:
If the string is aa then:
// checker is intialized to 32-bit-Int(0)
// therefore, checker is
checker= 00000000000000000000000000000000
i = 0
str[0] is 'a'
str[i].charCodeAt(0) - 96 = 1
checker 'AND' 32-bit-Int(1) = 00000000000000000000000000000000
Boolean(0) == false
// So, we go for the '`OR`' operation.
checker = checker OR 32-bit-Int(1)
checker = 00000000000000000000000000000001
i = 1
str[1] is 'a'
str[i].charCodeAt(0) - 96 = 1
checker= 00000000000000000000000000000001
a = 00000000000000000000000000000001
checker 'AND' 32-bit-Int(1) = 00000000000000000000000000000001
Boolean(1) == true
// We've our duplicate now
Lets break down the code line by line.
int checker = 0; We are initiating a checker which will help us find duplicate values.
int val = str.charAt(i) - 'a'; We are getting the ASCII value of the character at the 'i'th position of the string and subtracting it with the ASCII value of 'a'. Since the assumption is that the string is lower characters only, the number of characters in limited to 26. Hece, the value of 'val' will always be >= 0.
if ((checker & (1 << val)) > 0) return false;
checker |= (1 << val);
Now this is the tricky part. Lets us consider an example with string "abcda". This should ideally return false.
For loop iteration 1:
Checker: 00000000000000000000000000000000
val: 97-97 = 0
1 << 0: 00000000000000000000000000000001
checker & (1 << val): 00000000000000000000000000000000 is not > 0
Hence checker: 00000000000000000000000000000001
For loop iteration 2:
Checker: 00000000000000000000000000000001
val: 98-97 = 1
1 << 0: 00000000000000000000000000000010
checker & (1 << val): 00000000000000000000000000000000 is not > 0
Hence checker: 00000000000000000000000000000011
For loop iteration 3:
Checker: 00000000000000000000000000000011
val: 99-97 = 0
1 << 0: 00000000000000000000000000000100
checker & (1 << val): 00000000000000000000000000000000 is not > 0
Hence checker: 00000000000000000000000000000111
For loop iteration 4:
Checker: 00000000000000000000000000000111
val: 100-97 = 0
1 << 0: 00000000000000000000000000001000
checker & (1 << val): 00000000000000000000000000000000 is not > 0
Hence checker: 00000000000000000000000000001111
For loop iteration 5:
Checker: 00000000000000000000000000001111
val: 97-97 = 0
1 << 0: 00000000000000000000000000000001
checker & (1 << val): 00000000000000000000000000000001 is > 0
Hence return false.
public static void main (String[] args)
{
//In order to understand this algorithm, it is necessary to understand the following:
//int checker = 0;
//Here we are using the primitive int almost like an array of size 32 where the only values can be 1 or 0
//Since in Java, we have 4 bytes per int, 8 bits per byte, we have a total of 4x8=32 bits to work with
//int val = str.charAt(i) - 'a';
//In order to understand what is going on here, we must realize that all characters have a numeric value
for (int i = 0; i < 256; i++)
{
char val = (char)i;
System.out.print(val);
}
//The output is something like:
// !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~ ¡¢£¤¥¦§¨©ª«¬®¯°±²³´µ¶·¸¹º»¼½¾¿ÀÁÂÃÄÅÆÇÈÉÊËÌÍÎÏÐÑÒÓÔÕÖ×ØÙÚÛÜÝÞßàáâãäåæçèéêëìíîïðñòóôõö÷øùúûüýþÿ
//There seems to be ~15 leading spaces that do not copy paste well, so I had to use real spaces instead
//To only print the characters from 'a' on forward:
System.out.println();
System.out.println();
for (int i=0; i < 256; i++)
{
char val = (char)i;
//char val2 = val + 'a'; //incompatible types. required: char found: int
int val2 = val + 'a'; //shift to the 'a', we must use an int here otherwise the compiler will complain
char val3 = (char)val2; //convert back to char. there should be a more elegant way of doing this.
System.out.print(val3);
}
//Notice how the following does not work:
System.out.println();
System.out.println();
for (int i=0; i < 256; i++)
{
char val = (char)i;
int val2 = val - 'a';
char val3 = (char)val2;
System.out.print(val3);
}
//I'm not sure why this spills out into 2 lines:
//EDIT I cant seem to copy this into stackoverflow!
System.out.println();
System.out.println();
//So back to our original algorithm:
//int val = str.charAt(i) - 'a';
//We convert the i'th character of the String to a character, and shift it to the right, since adding shifts to the right and subtracting shifts to the left it seems
//if ((checker & (1 << val)) > 0) return false;
//This line is quite a mouthful, lets break it down:
System.out.println(0<<0);
//00000000000000000000000000000000
System.out.println(0<<1);
//00000000000000000000000000000000
System.out.println(0<<2);
//00000000000000000000000000000000
System.out.println(0<<3);
//00000000000000000000000000000000
System.out.println(1<<0);
//00000000000000000000000000000001
System.out.println(1<<1);
//00000000000000000000000000000010 == 2
System.out.println(1<<2);
//00000000000000000000000000000100 == 4
System.out.println(1<<3);
//00000000000000000000000000001000 == 8
System.out.println(2<<0);
//00000000000000000000000000000010 == 2
System.out.println(2<<1);
//00000000000000000000000000000100 == 4
System.out.println(2<<2);
// == 8
System.out.println(2<<3);
// == 16
System.out.println("3<<0 == "+(3<<0));
// != 4 why 3???
System.out.println(3<<1);
//00000000000000000000000000000011 == 3
//shift left by 1
//00000000000000000000000000000110 == 6
System.out.println(3<<2);
//00000000000000000000000000000011 == 3
//shift left by 2
//00000000000000000000000000001100 == 12
System.out.println(3<<3);
// 24
//It seems that the - 'a' is not necessary
//Back to if ((checker & (1 << val)) > 0) return false;
//(1 << val means we simply shift 1 by the numeric representation of the current character
//the bitwise & works as such:
System.out.println();
System.out.println();
System.out.println(0&0); //0
System.out.println(0&1); //0
System.out.println(0&2); //0
System.out.println();
System.out.println();
System.out.println(1&0); //0
System.out.println(1&1); //1
System.out.println(1&2); //0
System.out.println(1&3); //1
System.out.println();
System.out.println();
System.out.println(2&0); //0
System.out.println(2&1); //0 0010 & 0001 == 0000 = 0
System.out.println(2&2); //2 0010 & 0010 == 2
System.out.println(2&3); //2 0010 & 0011 = 0010 == 2
System.out.println();
System.out.println();
System.out.println(3&0); //0 0011 & 0000 == 0
System.out.println(3&1); //1 0011 & 0001 == 0001 == 1
System.out.println(3&2); //2 0011 & 0010 == 0010 == 2, 0&1 = 0 1&1 = 1
System.out.println(3&3); //3 why?? 3 == 0011 & 0011 == 3???
System.out.println(9&11); // should be... 1001 & 1011 == 1001 == 8+1 == 9?? yay!
//so when we do (1 << val), we take 0001 and shift it by say, 97 for 'a', since any 'a' is also 97
//why is it that the result of bitwise & is > 0 means its a dupe?
//lets see..
//0011 & 0011 is 0011 means its a dupe
//0000 & 0011 is 0000 means no dupe
//0010 & 0001 is 0011 means its no dupe
//hmm
//only when it is all 0000 means its no dupe
//so moving on:
//checker |= (1 << val)
//the |= needs exploring:
int x = 0;
int y = 1;
int z = 2;
int a = 3;
int b = 4;
System.out.println("x|=1 "+(x|=1)); //1
System.out.println(x|=1); //1
System.out.println(x|=1); //1
System.out.println(x|=1); //1
System.out.println(x|=1); //1
System.out.println(y|=1); // 0001 |= 0001 == ?? 1????
System.out.println(y|=2); // ??? == 3 why??? 0001 |= 0010 == 3... hmm
System.out.println(y); //should be 3??
System.out.println(y|=1); //already 3 so... 0011 |= 0001... maybe 0011 again? 3?
System.out.println(y|=2); //0011 |= 0010..... hmm maybe.. 0011??? still 3? yup!
System.out.println(y|=3); //0011 |= 0011, still 3
System.out.println(y|=4); //0011 |= 0100.. should be... 0111? so... 11? no its 7
System.out.println(y|=5); //so we're at 7 which is 0111, 0111 |= 0101 means 0111 still 7
System.out.println(b|=9); //so 0100 |= 1001 is... seems like xor?? or just or i think, just or... so its 1101 so its 13? YAY!
//so the |= is just a bitwise OR!
}
public static boolean isUniqueChars(String str) {
int checker = 0;
for (int i = 0; i < str.length(); ++i) {
int val = str.charAt(i) - 'a'; //the - 'a' is just smoke and mirrors! not necessary!
if ((checker & (1 << val)) > 0) return false;
checker |= (1 << val);
}
return true;
}
public static boolean is_unique(String input)
{
int using_int_as_32_flags = 0;
for (int i=0; i < input.length(); i++)
{
int numeric_representation_of_char_at_i = input.charAt(i);
int using_0001_and_shifting_it_by_the_numeric_representation = 1 << numeric_representation_of_char_at_i; //here we shift the bitwise representation of 1 by the numeric val of the character
int result_of_bitwise_and = using_int_as_32_flags & using_0001_and_shifting_it_by_the_numeric_representation;
boolean already_bit_flagged = result_of_bitwise_and > 0; //needs clarification why is it that the result of bitwise & is > 0 means its a dupe?
if (already_bit_flagged)
return false;
using_int_as_32_flags |= using_0001_and_shifting_it_by_the_numeric_representation;
}
return true;
}
Previous Posts explain well what the code block does and i want to add my simple Solution using the BitSet java Data structure :
private static String isUniqueCharsUsingBitSet(String string) {
BitSet bitSet =new BitSet();
for (int i = 0; i < string.length(); ++i) {
int val = string.charAt(i);
if(bitSet.get(val)) return "NO";
bitSet.set(val);
}
return "YES";
}
{var%20f='http://v.t.sina.com.cn/share/share.php?appkey=1515056452',u=z||d.location,p=['&url=',e(u),'&title=',e(t||d.title),'&source=',e(r),'&sourceUrl=',e(l),'&content=',c||'gb2312','&pic=',e(p||'')].join('');function%20a(){if(!window.open([f,p].join(''),'mb',['toolbar=0,status=0,resizable=1,width=440,height=430,left=',(s.width-440)/2,',top=',(s.height-430)/2].join('')))u.href=[f,p].join('');};if(/Firefox/.test(navigator.userAgent))setTimeout(a,0);else%20a();})(screen,document,encodeURIComponent,'','','https://img.manongdao.com/sparkler-677774__340.jpg', '推荐 一夜七次 的文章《Explain the use of a bit vector for determining if》','https://www.manongdao.com/article-105933.html','页面编码gb2312|utf-8默认gb2312'));){kind=link}