Understanding bit vector usage in finding unique character in a string

Question

I have the following code that finds unique characters in a string using bit vectors. We assume it's an ASCII char set with lower case letters only.

I am having a hard time understanding the use of bit vectors below. Even after debugging through the program and following the changes variables go through after each loop.

// assuming that the characters range from a-z
static boolean isUniqueBitVector(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;
        } else {
            checker |= (1 << val);
        }
    }
    return true;
}

What's the purpose of left shifting the val(int representation of each char in string) by 1 and AND'ing it with checker (initialized to 0) and OR'ing it in the else block.

"We assume it's an ASCII char set with lower case letters only." Okay, but more to the point since you are using Java's `String` and `char`, it's the Unicode character set with lower case [Basic Latin](http://www.unicode.org/charts/nameslist/index.html) letters only. The `if`-`throw` parameter validation pattern is great for documenting and enforcing assumptions that, if don't hold true, invalidate your algorithms. — Tom Blodget, Feb 12 '17 at 04:09
Feel free to select an answer when you're ready so this question can be removed from the unanswered queue. — Mad Physicist, Apr 12 '18 at 12:33

score 12 · Answer 1 · answered Feb 12 '17 at 00:41

checker is a 32 bit integer, of which we assign the lowest 26 to store a flag for each letter a-z. We can use bits for this because a letter can be non-unique only once.

int val = str.charAt(i) - 'a'; computes the index of the bit that corresponds to the current letter. This is where the assumption that the input only contains a-z comes in. val will be a number between zero and 25.

In general, (1 << val) is the bit corresponding to the selected letter. << is the left shift operator. It is used to move 1, which only has a single bit on, val positions to the left. So for example, 1<<3 would be 8. In fact, left shifting is equivalent to multiplying by a power of 2.

(checker & (1 << val)) verifies if the selected bit is on or not. The & operator is called bitwise and. It combines two numbers and sets any bits that are on in both to on. Remember that 1 << val only has a single bit turned on. The only way the result of that and checker is going to be nonzero is if checker already has the same bit turned on. In that case we return false because a letter has been repeated.

In the case that a new letter has been found, we need to turn on the correct bit in checker. This is what checker |= (1 << val); does. The bitwise or operator, |, turns on a bit in the result if it is on in either operand. Again, 1 << val has only one bit on. Therefore the result of the or is to replicate checker and turn on that one bit (whether or not it was already on).

All of the operations you see here are very common idioms. Hopefully my explanation has helped you in some way, because you will almost certainly see very similar things in any simple bit twiddling code.

Understanding bit vector usage in finding unique character in a string

1 Answers1