Explain the use of a bit vector for determining if

Question

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?

Answer 1

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;

}

Answer 2

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"

• First pass (i = t)

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)

• Second pass (i = e)

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

Answer 3

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;
}

Answer 4

Simple Explanation (with JS code below)

• An integer variable per machine code is a 32-bit array
• All bit wise operations are 32-bit
• They're agnostic of OS / CPU architecture or chosen number system of the language, e.g. DEC64 for JS.
• This duplication finding approach is similar to storing characters in an array of size 32 where, we set 0th index if we find a in the string, 1st for b & so on.
• A duplicate character in the string will have its corresponding bit occupied, or, in this case, set to 1.
• Ivan has already explained: How this index calculation works in this previous answer.

Summary of operations:

• Perform AND operation between checker & index of the character
• Internally both are Int-32-Arrays
• It is a bit-wise operation between these 2.
• Check if the output of the operation was 1
• if output == 1
  • The checker variable has that particular index-th bit set in both arrays
  • Thus it's a duplicate.
• if output == 0
  • This character hasn't been found so far
  • Perform an OR operation between checker & index of the character
  • Thereby, updating the index-th bit to 1
  • Assign the output to checker

Assumptions:

• We've assumed we'll get all lower case characters
• And, that size 32 is enough
• Hence, we began our index counting from 96 as reference point considering the ascii code for a is 97

Given 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