바이트의 세트 비트 패턴
https://stackoverflow.com/questions/662988
-
20-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
Joel은 바이트의 세트 비트 수를 그의 프로그래밍 질문으로 계산한다고 언급했습니다. 인터뷰에 대한 게릴라 가이드, 그리고 조회 테이블에서 발생하는 패턴을 활용하는 방법에 대해 이야기했습니다. 나는 패턴을 찾은 후에 그것에 관한 기사를 썼다.
요약:
Number of bits set in a byte in 16x16
0 1 1 2 1 2 2 3 1 2 2 3 2 3 3 4
1 2 2 3 2 3 3 4 2 3 3 4 3 4 4 5
1 2 2 3 2 3 3 4 2 3 3 4 3 4 4 5
2 3 3 4 3 4 4 5 3 4 4 5 4 5 5 6
1 2 2 3 2 3 3 4 2 3 3 4 3 4 4 5
2 3 3 4 3 4 4 5 3 4 4 5 4 5 5 6
2 3 3 4 3 4 4 5 3 4 4 5 4 5 5 6
3 4 4 5 4 5 5 6 4 5 5 6 5 6 6 7
1 2 2 3 2 3 3 4 2 3 3 4 3 4 4 5
2 3 3 4 3 4 4 5 3 4 4 5 4 5 5 6
2 3 3 4 3 4 4 5 3 4 4 5 4 5 5 6
3 4 4 5 4 5 5 6 4 5 5 6 5 6 6 7
2 3 3 4 3 4 4 5 3 4 4 5 4 5 5 6
3 4 4 5 4 5 5 6 4 5 5 6 5 6 6 7
3 4 4 5 4 5 5 6 4 5 5 6 5 6 6 7
4 5 5 6 5 6 6 7 5 6 6 7 6 7 7 8
첫 번째 행과 열은 정확히 동일하며 그리드의 각 위치는 해당 위치의 행 및 열에 첫 번째 값을 추가하여 계산할 수 있습니다. 이로 인해 8 비트 번호에 16 개의 항목이있는 조회 테이블 만 있으면 처음 16 개의 숫자 만 사용할 수 있습니다. 그런 다음 숫자 243의 세트 비트를 계산하려면 다음과 같습니다.
a = [0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4]
x = 243 / 16 => 15 # (int)
y = 243 % 16 => 3
a[x] + a[y] => 6
# Are there six bits set in the number 243?
243 = 11110011 # yep
다음 패턴은 NXN 그리드의 크기를 두 배로 늘릴 때마다 각 사분면이 각각 각 사분면에 0, 각 사분면에 각각 0, 1, 1 및 2를 추가하여 계산할 수 있다는 것이 었습니다.
# Make a 4x4 grid on the paper, and fill in the upper left quadrant with the values of the 2x2 grid.
# For each quadrant, add the value from that same quadrant in the 2x2 grid to the array.
# Upper left quad add 0 to each number from 2x2
0 1 * *
1 2 * *
* * * *
* * * *
# Upper right quad add 1 to each number from 2×2
0 1 1 2
1 2 2 3
* * * *
* * * *
# Lower left quad add 1 to each number from 2×2
0 1 1 2
1 2 2 3
1 2 * *
2 3 * *
# Lower right quad add 2 to each number from 2×2
0 1 1 2
1 2 2 3
1 2 2 3
2 3 3 4
이 프로세스를 두 번 더 반복하면 위에서 16x16 그리드를 얻을 수 있으므로 그리드에서 시작할 수있는 일종의 쿼드 트리 알고리즘이 있어야한다고 생각했습니다.
0 1
1 2
숫자 N이 주어지면 조회 테이블을 즉석에서 생성하고 비트 수를 파악하십시오. 그래서 내 질문/도전은 그렇게 할 알고리즘을 알아낼 수 있습니까?
해결책 2
Robert의 코드를 기반으로합니다 여기, 그것은 나누기 나 모듈러스 없이도 한 번의 교대로 대체 할 수 있습니다.
a = [0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4]
x = 243 >> 4 # 15 (same as dividing by 16)
y = 243 & 0x0f # 3 ( same as modding by 16)
result = a[x] + a[y] # 6 bits set
또는 C :
const unsigned char oneBits[] = {0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4};
unsigned char CountOnes(unsigned char x)
{
unsigned char results;
results = oneBits[x&0x0f];
results += oneBits[x>>4];
return results
}
모든 크기의 정수의 경우 바이트를 통과하고 빠른 조회를 할 수 있습니다.
def bits(n)
a = [0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4]
a[n >> 4] + a[n & 0x0f]
end
def setBits(n)
total = 0
while(n > 0)
total += bits(n&0xff)
n >>= 8
end
total
end
setBits(6432132132165432132132165436265465465653213213265465) # 78 bits set
이 답변에 만족합니다. 나는 더 복잡하고 Quadtree-esque가 효율적이지 않을 것이라는 것을 알았습니다. 나는 그것이 괜찮은 생각 실험이라고 생각했습니다.
다른 팁
이것은 어리석은 질문입니다! 256 대신 16 엔트리 테이블을 사용하여 세트 세트 수를 계산 한 첫 번째 예에서는 마술 같은 것이 아닙니다! 당신이 한 모든 일은 바이트의 처음 네 비트 (첫 번째 니블)에 설정된 비트 수를 계산 한 다음 두 번째 니블에서 두 개를 함께 추가하는 것입니다. X/16은 첫 번째 니블이고 X%16은 두 번째 니블입니다.
프로세스를 반복하면 이제 두 개의 비트에 대한 조회 테이블이 있고 각 쌍에 대해 한 번 4 번만 수행합니다. 극단적으로, 당신은 모든 비트를 하나씩 함께 추가하면 명백한 대답을 얻을 수 있습니다.
조회 테이블의 요점은 추가를 피하는 것입니다.
늦은 포스트를 실례하지만 방금 도전을 발견했습니다. 내 $ .02 (Brute Force)
Private Sub Button1_Click(ByVal sender As System.Object, _
ByVal e As System.EventArgs) Handles Button1.Click
For x As Integer = 0 To 255
Debug.WriteLine(bitsOn2(CByte(x)) & " " & Convert.ToString(x, 2).PadLeft(8, "0"c))
Next
End Sub
Private Function bitsOn(ByVal aByte As Byte) As Integer
Dim aBit As Byte = 1
For z As Integer = 0 To 7
If (aByte >> z And aBit) = aBit Then bitsOn += 1
Next
End Function
Dim aDict As New Dictionary(Of Integer, Integer)
Private Function bitsOn2(ByVal aByte As Byte) As Integer
If aDict.Count = 0 Then 'init dictionary
For x As Integer = 0 To 255
aDict.Add(x, bitsOn(CByte(x)))
Next
End If
Return aDict(aByte)
End Function
