[코딩인터뷰] 문제 5.3

문제 5.3

	#region Question 5.3
	/*
	* 양의 정수 x가 입력으로 주어진다고 하자.
	* 이 정수를 이진수로 표현했을 때 1인 비트의 개수가 n이라고 하자.
	* 이진수로 표현했을 때 1인 비트 개수가 n인 다른 정수 중에서
	* x보다 작은 것 중 가장 큰 정수와, x보다 큰 것 중 가장 작은 정수를 찾아라.
	*/
	// 책의 해답에서 제시된 수학적으로 문제를 푸는 방법
	public static int Q3_GetNextArith(int number)
	{
	var c = number;
	var c0 = 0;
	var c1 = 0;
	while (((c & 1) == 0) && (c != 0))
	{
	c0++;
	c >>= 1;
	}
	while ((c & 1) == 1)
	{
	c1++;
	c >>= 1;
	}
	/* If c is 0, then n is a sequence of 1s followed by a sequence of 0s. This is already the biggest
	* number with c1 ones. Return error.
	*/
	if (c0 + c1 == 31 || c0 + c1 == 0)
	{
	return -1;
	}
	/* Arithmetically:
	* 2^c0 = 1 << c0
	* 2^(c1-1) = 1 << (c0 - 1)
	* next = n + 2^c0 + 2^(c1-1) - 1;
	*/
	return number + (1 << c0) + (1 << (c1 - 1)) - 1;
	}
	public static int Q3_GetPrevArith(int number)
	{
	var temp = number;
	var c0 = 0;
	var c1 = 0;
	while (((temp & 1) == 1) && (temp != 0))
	{
	c1++;
	temp >>= 1;
	}
	/* If temp is 0, then the number is a sequence of 0s followed by a sequence of 1s. This is already
	* the smallest number with c1 ones. Return -1 for an error.
	*/
	if (temp == 0)
	{
	return -1;
	}
	while ((temp & 1) == 0 && (temp != 0))
	{
	c0++;
	temp >>= 1;
	}
	/* Arithmetic:
	* 2^c1 = 1 << c1
	* 2^(c0 - 1) = 1 << (c0 - 1)
	*/
	return number - (1 << c1) - (1 << (c0 - 1)) + 1;
	}
	#endregion

view raw Code_Q5_3.cs hosted with ❤ by GitHub

	[TestMethod]
	public void Q5_3()
	{
	Assert.AreEqual(0x00000001, BitManipulation.Q3_GetPrevArith(0x00000002));
	Assert.AreEqual(0x00000850, BitManipulation.Q3_GetPrevArith(0x00000860));
	Assert.AreEqual(0x17FFFFFF, BitManipulation.Q3_GetNextArith(0x0FFFFFFF));
	Assert.AreEqual(0x00000881, BitManipulation.Q3_GetNextArith(0x00000860));
	}

view raw Test_Q5_3.cs hosted with ❤ by GitHub