3
\$\begingroup\$

This is a program to return the sum of pairwise Hamming Distance of the binary string representation of a vector of integers. Please let me know how I can make this better?

int Solution::hammingDistance(const vector<int> &A) {
    vector<string> binrep;
    int N=A.size();
    int i,j, rem, n;
    for(i=0;i<N;i++){
        n=A[i];
        string bin;
        if (n == 0){
            bin.push_back((char)('0'));
            binrep.push_back(bin);
            continue;
        }
        while (n > 0) {
        rem = n % 2; 
        bin.push_back((char)('0' + rem));
        n /= 2;
        }
        binrep.push_back(bin);
    }
    int ans=0;
    for(i=0;i<N;i++){
        for(j=i+1;j<N;j++){
            int k = 0, count = 0;
            while (binrep[i][k] != '\0' && binrep[j][k] !='\0')
            {
                if (binrep[i][k] != binrep[j][k])
                    count++;
                k++;
            }
            if(binrep[i][k] == '\0' && binrep[j][k]!='\0'){
                while (binrep[j][k] !='\0'){
                    if(binrep[j][k]=='1')
                        count++;
                    k++;
                }
            }
            else if (binrep[i][k] != '\0' && binrep[j][k]=='\0'){
                while (binrep[i][k] !='\0'){
                    if(binrep[i][k]=='1')
                        count++;
                    k++;
                }
            }
            ans+=count*2;
            ans=ans%1000000007;
        }
    }
    return(ans);
}
\$\endgroup\$

closed as off-topic by πάντα ῥεῖ, Toby Speight, Graipher, Vogel612, Donald.McLean Jan 11 '18 at 16:35

This question appears to be off-topic. The users who voted to close gave this specific reason:

If this question can be reworded to fit the rules in the help center, please edit the question.

  • \$\begingroup\$ Is there any reason to represent ints as strings? \$\endgroup\$ – Costantino Grana Jan 9 '18 at 23:09
  • \$\begingroup\$ No. It is not a requirement. \$\endgroup\$ – Keerthana Gopalakrishnan Jan 9 '18 at 23:17
  • \$\begingroup\$ Then an obvious improvement is to compute the distance directly on the binary representation. \$\endgroup\$ – Costantino Grana Jan 9 '18 at 23:21
  • 3
    \$\begingroup\$ That should be mentioned somewhere in the question. Otherwise it looks like it would be part of calculating the Hamming distance between two numbers. \$\endgroup\$ – mkrieger1 Jan 9 '18 at 23:49
  • 1
    \$\begingroup\$ Welcome to Code Review! You'll receive better reviews if you show a complete example. For example, I recommend that you edit to show the necessary #include lines, the definition of Solution and a main() that shows how to call your function. It can really help reviewers if they are able to compile and run your program. \$\endgroup\$ – Toby Speight Jan 10 '18 at 11:38
5
\$\begingroup\$

Code Review

Never use C cast

The C cast is dangerously hard to spot. In C++ we have replaced this with four distinct cast operators that all do slightly different things. They are very easy to spot (as you should not really be doing cast anyway and when you do we want to be able to spot it easily for code review).

            bin.push_back((char)('0'));

So if this was C++ that would use the static cast.

            bin.push_back(static_cast<char>('0'));

But not really. Anything that is in single quotes '0' already has a type of char so you don't actually need to cast it.

            bin.push_back('0');

Also in this situation. you only push back one character. So why not just use assignment in the first place.

            bin = "0"; // much more clear.

Actually there is no need to even use the variable bin. In the next line you can simply push back a literal string.

            binrep.push_back(bin);

            // why not just
            binrep.push_back("0");

Use C++ classes where you can.

        while (n > 0) {
            rem = n % 2; 
            bin.push_back((char)('0' + rem));
            n /= 2;
        }

So you are building a binary version of the number in a string. Easier way to do that using std::bitset.

        std::bitset<8> value(n);
        bin.push_back(value.to_string()); // You may need to reverse
                                          // or something I did not pay
                                          // full attention to what you
                                          // were doing.

When looping over containers use the range based for.

    for(i=0;i<N;i++){

    // can be replaced by this.
    for(auto const& item: binrep) {

Look for standard algorithms where you have a loop:

This looks like you are counting.

                while (binrep[j][k] !='\0'){
                    if(binrep[j][k]=='1')
                        count++;
                    k++;
                } 

                // I think it may have been easier to write:
                count += std::count(std::begin(binrep[j]), std::end(binrep[j]), '1');

This is also self documenting as you can see what you are doing. The algorithm is appropriately named to make your actions obvious.

###BUG

            binrep[i][k] != '\0'

You can not look for a terminating \0 on a C++ std::string. Accessing beyond the end of the string is undefined behavior. If you want a C-String version to loop over you need to call c_str() on the object (but better to use a range based for.

Style

A lot of this (style) is preference and dependent on your team. I think it is important for the community to be consistent and have describes some common practices below. Others will inevitably disagree as this is opinion, refer to your teams style guide.

But your horizontal spacing (it does not exist) makes your code hard to read it is all packed together horizontally. It just makes the code horrible (and thus harder to read). Technically nothing wrong with that, but the whole point of coding is to make it easy to read for the next human that has to decipher your code.

for(i=0;i<N;i++){

// I would write it like this:

for(int i = 0; i < N; ++i) {

Your usage of braces ( {} ) is inconsistent. Neither version is wrong. But using two different styles is jarring (and again makes it hard to read).

        while (n > 0) {
            // STUFF
        }

   // and

        while (binrep[i][k] != '\0' && binrep[j][k] !='\0')
        {
        }

Always indent sub-blocks and always use braces {} around sub blocks.

        // Not indenting the sub block makes it hard to read.
        while (n > 0) {
        rem = n % 2; 
        bin.push_back((char)('0' + rem));
        n /= 2;
        }

        // Not using braces opens you up to maintenance problems.
        // larger than needed modifications when a bug is fixed.
        // thus reduced readability in the change log.
        //
        // There are also corner cases that are going where not
        // using the braces are going to be an error so prefer
        // to use them.
        if (binrep[i][k] != binrep[j][k])
            count++;

Declare variables one per line and at the point where they are used. This makes it easier to check types of local objects, and becomes much more important when your types have constructors and destructors.

    // Also the inconsistent use of space is jarring.
    int i,j, rem, n;

Variable names. Please use them. Modern code is supposed to be self documenting. So reading the variable name and how it is used is supposed to help me to understand the context of the code.

    // I have no idea what these do (rem: short for remainder?)
    int i,j, rem, n;


    for(int loop = 0; loop < size; ++loop) // Its a loop.

With naming. It's traditional to use an initial upper case letter for user defined types while an initial lower case letter is used for objects (variables/functions). This is important in C++ because types are so much more important than in C. We want to understand when we are referring to a user type and when we are referring to an object (the distinction is important and the use of visual cues can help make the code self documenting).

NOTE: The use of identifiers that are all uppercase is still (even in C++) traditionally reserved for macros. You should avoid their use for other things. N is an all uppercase identifier.

Pick a style and be consistent. Consistency is key in making code that is easy to maintain.

\$\endgroup\$
  • \$\begingroup\$ IIRC std::string specifically allows accessing the zero part as long as it is only a read. cppreference. \$\endgroup\$ – Incomputable Jan 10 '18 at 2:50
4
\$\begingroup\$

First and foremost, I think the conversion to strings is causing you more trouble than it's worth.

I'd start by computing the exclusive-or of two numbers. This will have a 1 bit where the bits on those inputs were different, and a 0 bit where they were identical. So after you compute the XOR, you just count the one-bits in the result.

Doing things this way, the core of the computation works out to something like this:

int hamming_distance(std::vector<int> const &input) { 
    int total = 0;
    for (int i=0; i<input.size(); i++)
        for (int j=i+1; j<input.size(); j++) {
            auto diff = input[i] ^ input[j];                
            total += 2 * std::bitset<32>(diff).count();
            total %= 1000000007;
        }
    return total;
}

There are many other ways to compute the Hamming weight of (number of bits set in) an integer. If you prefer not to use std::bitset, you might want to look at the answers to an old question on SO for some other possibilities.

Another possibility would be to convert to bitset first, then compute the xor of the two bitsets, and get the count on that result. I don't see a lot of reason to prefer one over the other.

\$\endgroup\$
  • \$\begingroup\$ Was about to add a bit about algorithms to my answer but you beat me to it. Damm. What he said. \$\endgroup\$ – Martin York Jan 9 '18 at 23:29
  • \$\begingroup\$ Why is each individual result multiplied by 2? \$\endgroup\$ – mkrieger1 Jan 9 '18 at 23:55
  • \$\begingroup\$ You take advantage of the fact that distance is commutative, so instead of computing all pairwise distances, you compute the distance between a and b and multiply it by 2, instead of computing also b and a. \$\endgroup\$ – Costantino Grana Jan 10 '18 at 0:03

Not the answer you're looking for? Browse other questions tagged or ask your own question.