Tag Archives: array

Unique number using bitwise operator

Follow me

Vinay Singh

Computer Teacher at Saint John's Academy
I am a GNU/Linux enthusiast and a computer science teacher by profession based at Allahabad, India. My hobbies include reading (mostly computer related stuff) and photography.
Follow me

Latest posts by Vinay Singh (see all)

A unique number can be defined as a positive integer without leading zeros, in which each digit occurs only once (no duplicate digit). There can be various methods to deunique numbertect whether or not a given positive integer is a unique number or not. I won’t be discussing methods which requires the number to be converted into a string as that would be inefficient in terms of space and time.

The approach which I am going to demonstrate in this post is to use a single short (integer) variable to store the presence(or absence) of each digit of an integer instead of multiple flags or an array. Note that a short variable consist of 16 bits (i.e. binary digit 0 or 1) and in this case we only need 10 bits to store the presence (or absence) of each digit. The idea is to read a bit corresponding to the required digit, if it is already 1 that means that the digit is repeated and false is returned. If the bit read is 0 then it is set as 1 to denote the presence of that particular digit. The last digit is for 0, the second last bit is for digit 1 and so on.

The java program to implement the above mentioned logic for unique number is as follows:

class UniqueNumber{
    public static boolean isUnique( int n ){
        short status=0;
        byte digit;
        for( int temp=n; temp>0; temp/=10 ){
            digit=(byte)(temp%10);
            if( (status & (1<<(digit))) >0 ) return false;
            else status |= 1<<(digit);
        }
        return true;
    }
    public static void main( String args[] ){
        System.out.println(isUniqueNumber(1234)); //1234 is a unique number
        System.out.println(isUniqueNumber(12342));//12342 is not a unique number
    }
}

The output of the above program to ascertain the unique number would be as follows:

true
false

The expression

1<<(digit)

is for shifting 1 towards the left for required number of bits. For example, if digit is 0 the expression it would remain 0, if digit is 1 the expression would result in 10, if digit is 2 the expression would result in 100 and so on.

The expression

status & (1<<(digit))

is for extracting the required bit from the variable status. Note that a.1=1 according to boolean algebra.

The expression

status |= 1<<(digit)

is a short-hand for

status = status | 1<<(digit)

The purpose of the above line is to set a particular bit because a+1=1 according to boolean algebra.