Search code examples
javabit-shiftshift

Detect duplicate in String using shift operator java

I have troubles understanding this code that detects duplicates in string.

int checker = 0;
    for(char ch : seed.toCharArray()){
        int val = ch - 'a';
        System.out.println(val);
        if ((checker & (1 << val)) > 0){ 
            // duplicate found
            break;
        }
        checker |= (1 << val);
    }

can someone explain me with an example how this works ?

Solution

  • Ok, say for example ch = 'c':

    int val = 'c' - 'a' = 2; //The char value for 'c' is two greater that that for 'a'

    then evaluate the if condition: 

    1 << 2

    means "shift 1 two places to the left", which gives us binary 100, or decimal 4.

    checker & 4

    means "bit-wise and" between checker, ie check if that particular bit is already set.

    if the bit was set, we are done, otherwise we perform

    c |= 4

    which means "c = c | 4", which is a bit-wise or that will set the bit corresponding to 'c' to 1.