###### tags: `math` `Public`
# 位元掃描器
## 目的
有一個非0的正數，以二進制表示，如何快速找到它二進制中最後的1所在位置。
例如，0101010010010100，其最後一個1所在位置為，從右數來第2個位置（從0開始編號）。

0|1|0|1|0|1|0|0|1|0|0|1|0|★"1"|0|0
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
15|14|13|12|11|10|9|8|7|6|5|4|3|★"2"|1|0|

## 轉化成只有一個1的方式
### 轉化公式一

x &= (~x+1)

### 轉化公式二

x &= -x

### 轉化範例表
a = 3932700031202623488
b = -3932700031202623488
c = a & b
a|0011|0110|1001|0011|1100|0001|1101|0111|1001|0000|0000|0000|0000|0000|0000|0000
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
b|1100|1001|0110|1100|0011|1110|0010|1000|0111|0000|0000|0000|0000|0000|0000|0000
c|0000|0000|0000|0000|0000|0000|0000|0000|0001|0000|0000|0000|0000|0000|0000|0000

經過 x & -x 操作以後，就能把末尾的1篩出來。原理是因為負數的存儲方式是以原碼的補碼，即符號位不變，每位取反再加1 。末尾連續的0取反以後都為1，所以加1以後會一直往前進位，直到原來為1的那一位，因為它取反以後這一位變成0了，就不會往前進位了。

### 範例程式碼

package main

import (
	"fmt"
	"unsafe"
)

func main() {
	a := int64(3932700031202623488)
	printActualMemory(a)
	b := -a
	printActualMemory(b)
	c := a & b
	printActualMemory(c)
}

func printActualMemory(a int64) string {
	this := ""
	for _, i := range *(*[8]byte)(unsafe.Pointer(&a)) {
		this = fmt.Sprintf("%08b", i) + this
	}
	fmt.Println(this)
	return this
}

## 取得位置方式

### 迭代循環 $O(n)$

for ( index = -1; x > 0; x >>= 1, ++index ) ;

### 二分搜索 $O(log_n)$

### 構造特殊數字進行位運算 $O(log_n)$

index = 0;
index += (!!(x & 0xAAAAAAAA)) * 1;
index += (!!(x & 0xCCCCCCCC)) * 2;
index += (!!(x & 0xF0F0F0F0)) * 4;
index += (!!(x & 0xFF00FF00)) * 8;
index += (!!(x & 0xFFFF0000)) * 16;

這種方式看上去比較巧，但是實際還是利用了二分搜索的思想。

### 哈希 $O(1)$
這種方式就比之前的方式都要高效了。

假設 x 有32位，所以末尾的1出現的可能只有32種。如果 x 為64，那就是64種可能，每一位上都有可能。通過哈希的方式 O(1) 的時間復雜度查詢出結果。

### 德布鲁因序列 $O(1)$
這種方式的原理也是哈希，但是這種方式比單純的哈希要快，因為它避免的取餘的計算。

並且是完美的哈希對應

## 參考
https://github.com/halfrost/Halfrost-Field/blob/master/contents/Go/go_s2_De_Bruijn.md