Please explain the code snippet that tells whether the given word is unique?

Question

Could someone please explain the working of this code snippet which tells if the given word is unique or not?

public static boolean isUniqueChars(String str) {
    if (str.length() > 128) {
        return false;
    }
    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;
}

I don't understand what is happening in the following two lines:

if ((checker & (1 << val)) > 0) return false;
checker |= (1 << val);

Thank you!

Vyacheslav · Answer 1 · 2017-07-09T14:39:35.053

0

Checker behaves like a Boolean array. Each element of this array stores whether a character is used or not. So, checker|= (1 << Val) stores a character into array.and if statement checks whether this char is used or not.

But it seems strange : < 128 comparison. because of the length of int is 32 bit.

edited Jul 09 '17 at 14:39

answered Jul 09 '17 at 14:35

Vyacheslav

26,359
19
112
194

Thanks, what exactly is this: ' |= '? And how exactly does it behave like an array since its declared as an int? – rowana Jul 09 '17 at 14:39
I was thinking the 128 check would be because there were 128 unique characters in total may be? – rowana Jul 09 '17 at 14:45

subro · Answer 2 · 2017-07-09T15:55:25.673

To Understand how it is working in bit level put Integer.toBinaryString() and check. Basically whenever you use bit wise operator in any integral value actual operation happen on there respective binary values.

public static boolean isUniqueChars(String str) {
        if (str.length() > 128) {
            return false;
        }       int checker = 0;
        for (int i = 0; i < str.length(); i++) {
            int val = str.charAt(i) - 'a';
            System.out.println("Actual Value " + val); // ASCII substraction
            System.out.println("Actual Value in Binary " + Integer.toBinaryString(val));
            System.out.println("Left Shift Value in Binary " + Integer.toBinaryString(1<<val));
            System.out.println("Operator Value is" + Integer.toBinaryString(checker & (1 << val))));
            if ((checker & (1 << val)) > 0) 
                return false;
            checker |= (1 << val); // checker = checker | (1<<val)
            System.out.println("Checker Value in Binary " + Integer.toBinaryString(checker));
        }
        return true;
    }

Run this and and check those print statement then you can identify how bit wise operator is working.

Logically: 1 is every time left shifted by ASCII substracted value and then BIT(or) is done with previous checker value. If current and checker value BIT(or) returns > 0 that means some bit position of both the value has 1. and thus its a repeating char. I know it sounds little complicate but take your time and debug it.

hope it helps you.

Please explain the code snippet that tells whether the given word is unique?

2 Answers2