Today, I took a look at this simple-looking problem. It’s mainly Bit Manipulation, where you need to find the number of bits required to change one Integer to another.
In about 15 mins, I was able to make a few good solutions. Tell me which one you like better! It’s mainly a matter of taste. Being that Integers have 32 bits in Java, no matter which algorithm you use, the time complexity will be O(1) and there is obviously no need for extra space so space complexity will also be O(1)
Find The Number of Bits Required to Change one Integer to Another
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
/* * @Author: Ajk Palikuqi * * @Question: How To Find The Number of Bits Required to Change one Integer to Another. */ package iqLib.bitLib; public class BitsToConvertInts { public static int getNumberOfBitsToConvertInts(int src, int dest) { int temp = src; int count = 0; while (temp != 0) { if ((src & 1) == (temp & 1)) { count++; } temp = temp >> 1; } return count; } public static int getNumberOfBitsToConvertInts2(int src, int dest) { int temp = src ^ dest; int count = 0; while (temp != 0); { count += (temp ^ 1); } return count; } public static int getNumberOfBitsToConvertIntsGeeky(int src, int dest) { int temp = src ^ dest; // Hamming Weight algorithm temp = (temp & 0XAAAAAAAA) >> 1 + (temp & 0X55555555); temp = (temp & 0XCCCCCCCC) >> 2 + (temp & 0X33333333); temp = (temp & 0XF0F0F0F0) >> 4 + (temp & 0X0F0F0F0F); temp = (temp & 0XFF00FF00) >> 8 + (temp & 0X00FF00FF); temp = temp >> 16 + (temp & 0X0000FFFF); return temp; } public static int getNumberOfBitsToConvertIntsEasy(int src, int dest) { return Integer.bitCount(src ^ dest); } } |
If you are interested in another language you could check-out Bit swaps required to convert an Integer in C
Hope you guys enjoyed some quick coding… and I’ll see you guys next time ;D
The following two tabs change content below.
If you like one of my posts the best way to support is give it a thumbs up, comment, or share it on social media 🙂
Latest posts by Ajk (see all)
- Find Median from Numbers Array - January 1, 2018
- Find Whether a Number Can Be the Sum of Two Squares - August 12, 2017
- How to Find Two Primes Whose Sum is Equal to a Number N - April 22, 2017