Discussion on: Hamming Distance - C++ Solution

[Pierre Gradot]

There is an easy solution to count the number of 1 bits in a value, with C++20:

#include <bit>

constexpr auto hammingDistance(unsigned int a, unsigned int b){
  return std::popcount(a ^ b);
}

See en.cppreference.com/w/cpp/numeric/...

[Gopi Gorantala]

Hey @pgradot,

This works fine, and the time is O(1). but the built-in popCount function would take O(k) time where k is the number of bits for an integer number.

So you code has to go through all of the bits present in a integer one-by-one.

But unlike Brian Kernighan’s Algorithm, which runs in 2 iterations to figure out the output using & operator for n and (n-1) elements.

[Pierre Gradot]

As Tony B mentionned below, I don't believe Big-O notation is relevant.

That consideration put aside, how do you know that std::popcount() is O(k)?

[Gopi Gorantala]

@pgradot, popCount returns the number of 1 bits in the value of x . How do you think it's doing? And how it knows if it's a 1 bit or 0 bit at any given position?

The popCount function runs through all the bit positions, which means k bits in any integer. So the time is directly proportional to number of bits present in an integer.

Also, Since it's an integer, and we knew that integers have fixed number of bits, hence at any point of time the time in running an algorithm is directly proportional to its bits.

**Note: **In small computations, big-O won't matter, but you should always write optimized algorithms in any software products.

[Pierre Gradot]

In both of your implementations for hammingDistance(), you start with a ^ b and then you count the bits, using 2 different techniques. Why on earth would std::popcount() would use a less optimized technique?

Furthermore, you say:

Time complexity: O(1). For a 32-bit integer, the algorithm would take at most 32 iterations.

Isn't that O(32) ?

Then you say:

Time complexity: O(1). The input size of the integer is fixed, we have a constant time complexity.

The integer is still 32-bit wide, so why do you have a different conclusion?

Note: a smart guy said almost 50 years ago that "premature optimization if the root of all evil"

[Gopi Gorantala]

Hey @pgradot ,

You covered everything, except that my first approach is not optimized and popCount fn runs through all the bit positions which isn't an optimized one as well.

Brian's algorithm is optimized, which is my second approach. Check LeetCode link below for explanation more on this.

Big-O simplification says, we can round it to the nearest one's.. O(32) by the way you're right, and is simplified and rounded to O(1), or constant time.

Why O(1)?
Here is what LeetCode experts has to say about Hamming Distance, check out their Brian's algorithm solution leetcode.com/problems/hamming-dist....... You'll understand... why this is a O(32) or in simple terms O(1) time.