Interview Preparation Bit Fiddling - Revision history

Proj user16: /* Interview Question : Bit Insertion between specified positions */

2016-12-13T07:38:43Z

‎Interview Question : Bit Insertion between specified positions

Proj user16: /* Interview Question : Next largest integer */

2016-12-13T07:18:04Z

‎Interview Question : Next largest integer

Proj user16 at 07:17, 13 December 2016

2016-12-13T07:17:26Z

Proj user16: /* Swap all odd and even bits */

2016-12-13T04:14:47Z

‎Swap all odd and even bits

Proj user16 at 01:12, 12 December 2016

2016-12-12T01:12:07Z

Proj user16: /* Bit Flip to convert from Integer A to B */

2016-12-11T05:25:32Z

‎Bit Flip to convert from Integer A to B

Proj user16: /* Bit Flip to convert from Integer A to B */

2016-12-11T05:24:52Z

‎Bit Flip to convert from Integer A to B

Proj user16 at 05:18, 11 December 2016

2016-12-11T05:18:37Z

Proj user16 at 03:42, 11 December 2016

2016-12-11T03:42:27Z

Preet at 22:35, 7 July 2013

2013-07-07T22:35:30Z

@@ Line 156: / Line 156: @@
 	/* Create a mask value to clear bit a through b in x.
 	 * Example: a = 0, b = 4. Result should be 11100000.
-	 * For simplicity, use just 8 bits for example.
+	 * For simplicity, I use just 8 bits for example.
 	 */
 	int allOnes = ~0;
@@ Line 175: / Line 175: @@
 </syntaxhighlight>
 <BR/>
 == Interview Question : Next largest integer ==
 '''''Task:''''' Given a positive integer, we have to print the next largest integer with the same number of 1 bits in their binary representation.

@@ Line 209: / Line 209: @@
 	//Error if x = 11..1100...00, because there is no bigger number with
-	//number of 1s.
+	//same number of 1s.
 	if (c0 + c1 == 31 || c0 + c1 == 0)
+	{

← Older revision		Revision as of 07:17, 13 December 2016
Line 174:		Line 174:
	}		}
	</syntaxhighlight>		</syntaxhighlight>
		+	<BR/>
		+	== Interview Question : Next largest integer ==
		+	'''''Task:''''' Given a positive integer, we have to print the next largest integer with the same number of 1 bits in their binary representation.
		+	<br>
		+	'''''Approach:'''''
		+	<br>
		+	Example : Let the input number be 13948 with binary representation 11011001111100
		+	<br>
		+	Step 1: Flip rightmost non trailing zero. Call this position '''''p'''''. This would increase the size of integer '''''x''''' but we have one too many one and ones too few zeros. Binary representation now becomes 11011011111100
		+	<br>
		+	Step 2: Let '''''c1''''' be the number of ones to the right of '''''p''''' and '''''c0''''' be the number of zeroes to the right of '''''p'''''. For this example, '''''c0 = 2''''' and '''''c1 = 5'''''. Clear bits to the right of '''''p'''''. Binary representation now becomes 11011010000000.
		+	<br>
		+	Step 3: Add in '''''c1-1''''' ones to the right. Binary representation now - 11011010001111. This is our required number - 13967
		+	<br>
		+	<syntaxhighlight lang="c">
		+	int nextGreater(int x)
		+	{
		+	// Compute c0 and c1
		+	int c = x;
		+	int c0 = 0;
		+	int c1 = 0;
		+
		+	while (((c & 1) == 0) && (c != 0))
		+	{
		+	c0++;
		+	c >>= 1;
		+	}
		+
		+	while (((c & 1) == 1))
		+	{
		+	c1++;
		+	c >>= 1;
		+	}
		+
		+	//Error if x = 11..1100...00, because there is no bigger number with
		+	//number of 1s.
		+	if (c0 + c1 == 31 \|\| c0 + c1 == 0)
		+	{
		+	return -1;
		+	}
		+
		+	int p = c0 + c1; // Rightmost non trailing 0.
		+
		+	x \|= (1 << p); // Flip rightmost non trailing 0.
		+	x &= ~((1 << p) - 1); // Clear all bits to the right of p
		+	x \|= (1 << (c1 - 1)) -1; // Insert c1-1 ones on the right and we are done
		+	return x;
		+	}
		+	</syntaxhighlight>
		+
		+	<BR/>

@@ Line 109: / Line 109: @@
 <BR/>
 == Bit Flip to convert from integer A to B ==
 This function determines the number of bits you would need to flip to convert from integer A to integer B.

@@ Line 136: / Line 136: @@
+	}
 	return count;
+}
 </syntaxhighlight>

@@ Line 119: / Line 119: @@
+{
 	int count = 0;
-	for(int z = x^y; z != 0; z = z>>1)
+	for(int z = x^y; z != 0; z = z >> 1)
+	{
 		count += z & 1;

@@ Line 105: / Line 105: @@
      return 0;
+}
 </syntaxhighlight>

@@ Line 73: / Line 73: @@
      uint8_t low_nibble  = (num & 0x0F);
      return (low_nibble << 4) | (high_nibble);
+}
 </syntaxhighlight>

@@ Line 59: / Line 59: @@
 uint32_t invert_bit(uint32_t num, uint32_t bit_pos)
+{
-     /* TODO */
+     return num xor (1 << bit_pos); // xor is a valid operator
+}
 </syntaxhighlight>