13.1 位運(yùn)算

Lua語言從 5.3 版本開始提供了針對數(shù)值類型的一組標(biāo)準(zhǔn)位運(yùn)算符。與算術(shù)運(yùn)算符不同的是，位運(yùn)算符只能用于整型數(shù)。位運(yùn)算符包括，&按位與、|按位或、~按位異或、>>邏輯右移、<<邏輯左移，~一元運(yùn)算符按位取反。（注意，^在 Lua 語言中代表冪運(yùn)算）。

print(string.format("%x", 0xff & 0xabcd))    -->    cd
print(string.format("%x", 0xff | 0xabcd))    -->    abff
print(string.format("%x",  0xaaaa ~ -1))    -->    ffffffffffff5555
print(string.format("%x",  ~0))    -->    ffffffffffffffff

移位數(shù)是負(fù)數(shù)表示向相反的方向以為，即 a >> n 與 a << -n 等價(jià)：

print(string.format("%x", 0xff << 12))    -->    ff000
print(string.format("%x", 0xff >> -12))    -->    ff000

如果移位數(shù)等于或大于整型表示的位數(shù)，由于所有的位都從結(jié)果中移出了，所以結(jié)果是 0。

13.2 無符號整型數(shù)

加法減法和乘法操作對于有符號整型數(shù)和無符號整型數(shù)是一樣的，關(guān)系運(yùn)算符對于有符號整型數(shù)和無符號整型數(shù)是不一樣的，當(dāng)比較具有不同符號位的整型數(shù)時(shí)就會出現(xiàn)問題。對于有符號整型數(shù)而言，符號位被置位的整數(shù)更小，因?yàn)樗淼氖秦?fù)數(shù)：

print(0x7fffffffffffffff < 0x8000000000000000)    -->    false

如果把兩個整型數(shù)都當(dāng)作無符號的，那么結(jié)果顯然不對。因此，我們需要使用一種不同的操作來比較無符號整型數(shù)。Lua 5.3 提供了函數(shù) math.ult（unsigned less than）來完成這個需求。

print(math.ult(0x7fffffffffffffff, 0x8000000000000000))    -->    true

另一種方式是再比較之前先去除符號位：

local mask = 0x8000000000000000
print((0x7fffffffffffffff ~ mask) < (0x8000000000000000 ~mask))    -->    true

無符號數(shù)和有符號數(shù)的除法也不一樣，示例 13.1 給出了一種無符號除法的算法：

示例 13.1 無符號除法

---@return number
---@param n number
---@param d number
function udiv(n, d)
    if d < 0 then
        if math.ult(n, d)
        then
            return 0        --被除數(shù)小于除數(shù)，結(jié)果肯定為 0
        else
            return 1        --如果 n 比 d 大那么最多也不可能商到 2 ，因?yàn)樵偕?2 就多一位丟失了
        end
    end
    local q = ((n >> 1) // d) << 1      --先右移算完再左移
    local r = n - q * d                 --商乘以除數(shù) 與被除數(shù)做差
    if not math.ult(r, d)
    then
        q = q + 1                       --如果 r 算出來的差值 比除數(shù)還要大，說明還可以再商 1 
    end
    return q
end

第一個比較（d<0）等價(jià)于比較 d 是否大于 2⁶³。如果大于，那么商只能是 1 或者 0（取決于被除數(shù) n 比 d 大還是小）。否則，我們使被除數(shù)右移一位，然后除以除數(shù)，再把結(jié)果乘以2。右移之后左移還原了原來的除法。
總體上說，floor(floor(n / 2) / d) * 2與floor(((n / 2) / d) * 2) 并不等價(jià)。不過，要證明它們之間最多相差 1 并不困難。因此，算法計(jì)算了余數(shù)，然后判斷余數(shù)是否比除數(shù)大，如果余數(shù)比除數(shù)大則糾正商 +1 即可。
無符號整型數(shù)和浮點(diǎn)型數(shù)之間的轉(zhuǎn)換需要進(jìn)行一些調(diào)整。要把一個無符號整型數(shù)轉(zhuǎn)換為浮點(diǎn)型數(shù)，可以先將其轉(zhuǎn)換成有符號整型數(shù)，然后通過取模運(yùn)算糾正結(jié)果。

local u = 11529215046068469760
local f = (u + 0.0) % 2 ^ 64
print(string.format("%f", f))    -->11529215046068469760.000000

要把一個浮點(diǎn)型書轉(zhuǎn)換為無符號整型數(shù)，可以使用如下的代碼：

local f = 0xA000000000000000.0
local u = math.tointeger(((f + 2 ^ 63) % 2 ^ 64) - 2 ^ 63)
print(string.format("%x", u))    -->    a000000000000000

加法把一個大于 2⁶³ 的數(shù)轉(zhuǎn)換為一個大于 2⁶⁴ 的數(shù)，取模運(yùn)算把這個數(shù)限制到 [0,2⁶³) 范圍內(nèi)，然后通過減法把結(jié)果變成一個“負(fù)值”。對于小于 2⁶³ 的值，加法結(jié)果小于 2⁶⁴，所以取模運(yùn)算沒有任何效果，之后的減法則把它恢復(fù)到了之前的值。

13.5 練習(xí)

• 練習(xí) 13.1：請編寫一個函數(shù)，該函數(shù)用于進(jìn)行無符號整型數(shù)的取模運(yùn)算。

這一題我試著做了一下發(fā)現(xiàn)極其復(fù)雜，我查到一個計(jì)算公式：return y<=x and x<0 and x-y or y<0 and x or ((x>>1)%y*2+(x&1)-y)%y，這個相當(dāng)于使用了短路原理來對結(jié)果進(jìn)行條件輸出，適當(dāng)增加括號：return (y<=x and x<0 and x-y) or (y<0 and x) or (((x>>1)%y*2+(x&1)-y)%y)
首先我們要認(rèn)清一點(diǎn)是，Lua 默認(rèn)是有符號數(shù)，現(xiàn)在我們將其視為無符號數(shù)來進(jìn)行處理，那么任何負(fù)數(shù)值都意味著它是超出 2⁶³ - 1 的大數(shù)值。
第一個括號內(nèi)的意思是，首先除數(shù)比被除數(shù)小，然后被除數(shù)小于 0，也就是說兩個參數(shù)都是大數(shù)值，但無論怎樣也不會商到1，因?yàn)檫_(dá)到2倍或以上時(shí)數(shù)據(jù)已經(jīng)溢出了，因此直接作差就可以得到模。
第二個括號的意思是，如果除數(shù)是大數(shù)值而被除數(shù)不是，那么取模結(jié)果就是被除數(shù)本身。
第三個括號的意思是，在除數(shù)不是大數(shù)值時(shí)，無論被除數(shù)是不是大數(shù)值均可以進(jìn)行通用的計(jì)算。

---@return number
---@param n number number
---@param m number mod
function UnsignedMod(n, m)
    return m<=n and n<0 and n-m or m<0 and n or ((n >> 1) % m * 2 + (n & 1) - m ) % m
end

local x = 0x7fffffffffffffff
local y = 0x8000000000000000
--local x = 6
--local y = 15

print(y % x)    -->    9223372036854775806
print(UnsignedMod(y, x))    -->    1

• 練習(xí) 13.2：請實(shí)現(xiàn)計(jì)算 Lua 語言中整型數(shù)所占位數(shù)的不同方法。

--- 通過反復(fù)傳入和傳出外部變量 size 的值，最終確定什么時(shí)候會報(bào)錯，當(dāng)報(bào)錯時(shí)就知道整型數(shù)的大小了
---@return number
---@param size number
function SizeOfInteger(size)
    local x = string.pack("i", 1 << size)
    print(size)
    return size + 1
end


local size = 0
while true do
    size = assert(SizeOfInteger(size))
end

在打印完 30 之后，程序報(bào)錯，說明參數(shù)為 i 的時(shí)候 size最大為 30 位，但是當(dāng)參數(shù)換成 j 以后，程序會進(jìn)入死循環(huán)，這說明 lua_integer 類型的大小至少是 64 位，由于 64 位系統(tǒng)最多容納 64 位數(shù)據(jù)，所以數(shù)據(jù) 1 已經(jīng)被推到有效位之外了，得到 0，所以永遠(yuǎn)不會報(bào)錯。

• 練習(xí) 13.3：如何判斷一個指定整數(shù)是不是 2 的整數(shù)次冪？

2 的整數(shù)次冪二進(jìn)制的特點(diǎn)為，除了最高位以外均為0（1 特殊 只有一個 1），因此只需要對數(shù)值 -1 然后進(jìn)行與，看結(jié)果是否為 0 即可。

---@return boolean
---@param n number
function IsAPowerOfTwo(n)
    n = math.tointeger(n)
    if n <= 0 then
        return false
    end

    local temp = n - 1

    return (temp & n) == 0
end

print(IsAPowerOfTwo(-1))    -->    false
print(IsAPowerOfTwo(0))    -->    false
print(IsAPowerOfTwo(1))    -->    true
print(IsAPowerOfTwo(2))    -->    true
print(IsAPowerOfTwo(3))    -->    false
print(IsAPowerOfTwo(4))    -->    true

• 練習(xí)13.4：請編寫一個函數(shù)，該函數(shù)用于計(jì)算指定整數(shù)的漢明權(quán)重（一個數(shù)的漢明權(quán)重是其二進(jìn)制表示中 1 的個數(shù)）。

---@return number
---@param n number
function HammingWeight(n)
    n = math.tointeger(n)
    local count = 0
    while n > 0 do
        n = n & (n - 1)
        count = count + 1
    end
    return count
end

for i = 0, 5 do
    print(HammingWeight(i))
end

• 練習(xí) 13.5：請編寫一個函數(shù)，該函數(shù)用于判斷指定整數(shù)的二進(jìn)制表示是否為回文數(shù)。

require("utils.ToBinaryString")

---@return boolean
---@param n number
function IsAPalindrome(n)
    local str
    local t = {}
    while n > 0 do
        table.insert(t, n & 1)
        n = n >> 1
    end

    str = table.concat(t)
    return str == string.reverse(str)
end

for i = 0, 8 do
    print(i, ToBinaryString(i), IsAPalindrome(i))
end

--------------------

0       true
1   1   true
2   10  false
3   11  true
4   100 false
5   101 true
6   110 false
7   111 true
8   1000    false

附上我自定義的工具類

--- 用于把給定的整形數(shù)轉(zhuǎn)換成二進(jìn)制形式的字符串
---@return string
---@param n number
function ToBinaryString(n)
    local t = {}
    while n > 0 do
        table.insert(t, n & 1)
        n = n >> 1
    end

    return string.reverse(table.concat(t))
end

• 練習(xí) 13.6：請?jiān)?Lua 語言中實(shí)現(xiàn)一個比特?cái)?shù)組，該數(shù)組應(yīng)支持如下的操作：
  newBitArray(n) （創(chuàng)建一個具有 n 個比特的數(shù)組）。
  setBit(a, n, v)（將布爾值 v 賦給數(shù)組 a 的第 n 位）
  testBit(a, n)（將第 n 位的值作為布爾值返回）。

BitArray = {
    array = {},

    setBit = function(self, n, v)
        self.array[n] = v
    end,
    testBit = function(self, n)
        return self.array[n]
    end
}

function BitArray:new(n)
    local o = {array = {}}
    for i = 1, n do
        table.insert(o.array, false)
    end
    self.__index = self
    setmetatable(o, self)
    return o
end

local ba = BitArray:new(3)
print(ba.testBit(ba,1))    -->    false
print(ba.testBit(ba,2))    -->    false
print(ba.testBit(ba,3))    -->    false
print(ba.testBit(ba,4))    -->    nil
ba.setBit(ba,1,true)
print(ba.testBit(ba,1))    -->    true

• 練習(xí) 13.7：假設(shè)有一個以一系列記錄組成的二進(jìn)制文件，其中的每一個記錄的格式為：
  struct Record{
  int x;
  char[3] code;
  float value;
  };
  請編寫一個程序，該程序讀取這個文件，然后輸出 value 字段的總和。

不會