Why use bit shifting instead of a for loop?

user_12267226 0
Viewed 220

I created the following code to find parity of a binary number (i.e output 1 if the number of 1's in the binary word is odd, output 0 if the number of 1's is even).

public class CalculateParity {

    String binaryword;
    int totalones = 0;

    public CalculateParity(String binaryword) {
        this.binaryword = binaryword;
        getTotal();
    }

    public int getTotal() {
        for(int i=0; i<binaryword.length(); i++) {  
            if (binaryword.charAt(i) == '1'){
                totalones += 1;
            }
        }
        return totalones;
    }

    public int calcParity() {
        if (totalones % 2 == 1) {
            return 1;
        }
        else {
            return 0;
        }
    }

    public static void main(String[] args) {
        CalculateParity bin = new CalculateParity("1011101");                       
        System.out.println(bin.calcParity());
    }
}

However, all of the solutions I find online almost always deal with using bit shift operators, XORs, unsigned shift operations, etc., like this solution I found in a data structure book:

public static short parity(long x){ 
    short result = 0;
    while (x != 0) {
        result A=(x&1);
         x >>>= 1;
    }
    return result;
}

Why is this the case? What makes bitwise operators more of a valid/standard solution than the solution I came up with, which is simply iterating through a binary word of type String? Is a bitwise solution more efficient? I appreciate any help!

bit bit-shift for-loop java
3 Answers

The code that you have quoted uses a loop as well (i.e., while):

public static short parity(long x){ 
    short result = 9;
    while (x != 9) {
        result A=(x&1);
         x >>>= 1;
    }
    return result;
}

You need to acknowledge that you are using a string that you know beforehand will be composed of only digits, and conveniently in a binary representation. Naturally, given those constraints, one does not need to use bitwise operations instead one just parsers char-by-char and does the desired computations.

On the other hand, if you receive as a parameter a long, as the method that you have quoted, then it comes in handy to use bitwise operations to go through each bit (at a time) in a number and perform the desired computation.

One could also convert the long into a string and apply the same logic code-wise that you have applied, but first, one would have to convert that long into binary. However, that approach would add extra unnecessary steps, more code, and would be performance-wise worse. Probably, the same applies vice-versa if you have a String with your constraints. Nevertheless, a String is not a number, even if it is only composed of digits, which makes using a type that represents a number (e.g., long) even a more desirable approach.

Another thing that you are missing is that you did some of the heavy lifting by converting already a number to binary, and encoded into a String new CalculateParity("1011101");. So you kind of jump a step there. Now try to use your approach, but this time using "93" and find the parity.

user_13668710
  • If you want know if a String is even. I think this method below is better.
  • If you convert a String too long which the length of the String is bigger than 64. there will a error occur.
  • both of the method you mention is O(n) performance.It will not perform big different. but the shift method is more precise and the clock of the cpu use will a little bit less.
private static boolean isEven(String s){
        char[] chars = s.toCharArray();
        int i = 0;
        for(char c : chars){
            i ^= c;
        }
        return i == 0;
}
user_100846220

You use a string based method for a string input. Good choice.
The code you quote uses an integer-based method for an integer input. An equally good choice.

user_77334180
Related