C# | Kernighan’s Algorithm | Super Fast
Intuition\nKernighan\u2019s Algorithm is a quick way to count how many bits are on in a given number. The explanation of this algorithm is in the comments of th
# Intuition\nKernighan\u2019s Algorithm is a quick way to count how many bits are on in a given number. The explanation of this algorithm is in the comments of the BitCount function. \n\nSome simple bitwise operations on our inputs will give us numbers whose bits we can count to give us our answer. Doing it this way will require use to loop over two numbers, however we will save numerous if checks and bitshifts, and so it should be faster than the brute force methods.\n\n# Approach\nFirst implement Kernighan\'s Algorithm to count bits.\n\nIn order to find bits where a flip of some kind is needed we can simply XOR c with the target (a or b). An XOR is on only if the bit is on in one number but not the other. All of the bits that are on after the XOR will require at least one flip. \n\nNow we just need to find the bits that are on in our XOR result and BOTH a AND b. These are the bits that need double counted.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(1)$$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(1)$$\n# Code\n```\npublic class Solution {\n    public int MinFlips(int a, int b, int c) {\n        int flips = 0;\n        int or = a | b;\n        //xor\'ing will tell us places where \n        //  1) c is on but neither a or b is\n        //  2) c is off but a or b or both is on\n        int xor = c ^ or;\n        //at least one bit needs flipped for each bit that is on\n        flips = this.BitCount(xor);\n        //now we just need to count once more\n        //the places where both a and b need flipped\n        int dblcount = xor & a & b;\n        flips += this.BitCount(dblcount);\n\n        return flips;\n    }\n\n    public int BitCount(int x) {\n        /*\n        Brian Kernighan\u2019s Algorithm\n        ---------------------------\n        Relies on the following observation about what happens \n        when you subtract 1 from a number in binary.\n        E.g.\n        52: 0011 0100\n        51: 0011 0011\n\n        Notice we could describe subtracting 1 in the \n        following way:\n        Find the first bit from the right that is set (==1).\n        That bit and all the bits to its right will flip.\n        Any set bits to the left stay.\n\n        Now, if we AND those two numbers (x AND x-1) together \n        we are left with\n        0011 0000\n\n        So we went from 3 set bits to 2. \n        If we repeat this procedure and count how many times we \n        do it before we reach zero, we will have our answer.\n        */\n        int count = 0;\n        while (x > 0){\n            count++;\n            x &= (x - 1);\n        }\n        return count;\n    }\n}\n```\nWould greatly appreciate an upvote if you found this useful or interesting.
['C#']