package com.akasiyanik.interview.ch4.pr1;

/**
 * Improved algorithm
 * Complexity - O(k), k - number of 1s in word
 * We store result mod 2 (using ~ XOR operator)
 *
 * @author akasiyanik
 *         6/21/17
 */
class ImprovedParityCalculator implements BinaryWordParityCalculator {

    @Override
    public short parity(long x) {
        long number = x;
        short result = 0;
        while (number != 0) {
            number = number & (number - 1); // Drop the lowest set bit of word
            result ^= 1;
        }
        return result;
    }
}
