비트 작업 코딩 인터뷰 크래킹

Question

저는 CTCI의 비트 조작과 관련된 첫 번째 문제를 해결하기 위해 노력해 왔으며 작성자가 최종 솔루션에서 정확하게 마스크를 어떻게 작성했는지 파악할 수 없습니다. 누군가 "int left", "int right"및 "int mask"에 대한 계산을 설명 할 수 있습니까? 그가 제공 한 예를 위해이 선들이 구체적으로 계산하는 것을 보는 것은 좋을 것입니다.

질문 : 두 개의 32 비트 숫자 N과 M과 두 개의 비트 위치 i와 j가 제공됩니다. 메서드를 작성하여 N에서 i와 j 사이의 모든 비트를 M과 동일하게 설정합니다 (예 : M은N의 하위 문자열이되고 j에서 시작). 예 : 입력 : N = 10000000000, M = 10101, I = 2, J = 6 출력 : N = 10001010100

public static int updateBits(int n, int m, int i, int j) { 
int max = ~0; /* All 1’s */ 

// 1’s through position j, then 0’s 
int left = max - ((1 << j) - 1); 

// 1’s after position i 
int right = ((1 << i) - 1); 

// 1’s, with 0s between i and j 
int mask = left | right; 

// Clear i through j, then put m in there 
return (n & mask) | (m << i); 
} 

Answer 1

는 "INT 오른쪽", "왼쪽하는 int"에 대한 계산을 설명, 및 "INT 마스크"

• (1 << j)

  // 1’s through position j, then 0’s 
  int left = max - ((1 << j) - 1); 
  

  는 j 세트 1
012,351,641 행 위치에서 단지 비트를 가지고
• ((1 << j) - 1) (1 감산)는, 상기의 비트의 보수를 산출 전 위치 (전체 1 감산) 1
• max - ((1 << j) - 1)-j 세트 (오른쪽) 아래의 모든 j 비트를 산출한다. 이자형. 0

내지 E (왼쪽)과 1 설정 위치 j 등 위의 모든 비트 세트 및 아래 j 비트. 지.

• (1 << i)

  j   1<<j   (1<<j)-1  ~0-((1<<j)-1) 
  ------------------------------------------------------- 
  0  000000000001  000000000000  111111111111 
  1  000000000010  000000000001  111111111110 
  2  000000000100  000000000011  111111111100 
  3  000000001000  000000000111  111111111000 
  4  000000010000  000000001111  111111110000 
  5  000000100000  000000011111  111111100000 
  6  000001000000  000000111111  111111000000 
  ... 
  

  // 1’s after position i 
  int right = ((1 << i) - 1); 
  

  는 i 세트 (1 감산) 1
• ((1 << i) - 1) 행 위치에서 단지 비트를 가지고 위치 i 세트 (오른쪽) 아래의 모든 i 비트 수득 1

e. 지.

i   1<<i   (1<<i)-1 
------------------------------------- 
0  000000000001  000000000000 
1  000000000010  000000000001 
2  000000000100  000000000011 
... 

// 1’s, with 0s between i and j 
int mask = left | right; 

제가 = 2, J = 6 :

left  111111000000 
right  000000000011 
|   ------------ 
mask  111111000011 

// Clear i through j, then put m in there 
return (n & mask) | (m << i); 

• (n & mask) 달리 댓글이 비트를 클리어 0,123,912,796 7,586,254,974,563,210 j 내지 -1 만
• (m << i)는 예에 마스크 n

-

(n & mask) | (m << i) 논리합 시프트 값의 비트를 소망 비트 위치에 설정되는 값으로 이동 (상기 mask 참조)

을

이 예제 값이 올바른 결과를 가져 오지만, updateBits()의 구현이 사실임을 알 수 있습니다 비트 위치 j 보낸 1 비트 만 위치 j 포함하는 좌측 및 하지에 maskleft 요구의 일부이며, 문자열에 포함되어있어 Y의 문제가 마스크 아웃된다. 잘못은 e를 보여준다. 지. 값 N = 11,111,111,111와 m = 00000, I = 2, J = 6 :

n  011111111111 
mask 111111000011 
&  ------------ 
n&mask 011111000011 
m<<i 000000000000 
|  ------------ 
     011111000011 

값 m 비트 위치에 투입 한 I-J-1 만.

오류는

int left = max - ((1 << j+1) - 1); 

에

int left = max - ((1 << j) - 1); 

를 변화시킴으로써 보정 될 수있다