Open bxb100 opened 6 months ago
Salt Lake City;10.3
的 bytes:
byte[19] { 83, 97, 108, 116, 32, 76, 97, 107, 101, 32, 67, 105, 116, 121, 59, 49, 48, 46, 51 }
按 Long 64bits 来分割的话,为(这里都是大端,后面使用需要 Long.reverseBytes
):
// 83, 97, 108, 116, 32, 76, 97, 107
// 6008202623902835051L hex: 0x53616C74204C616B
// 101, 32, 67, 105, 116, 121, 59, 49
// 7286898317290191665L hex: 0x6520436974793B31
// 48, 46, 51
// 0x302E33L
可以看到
final long match = word ^ 0x3B3B3B3B3B3B3B3BL;
long mask = ((match - 0x0101010101010101L) & ~match) & 0x8080808080808080L;
主要是判断 bytes 里面有没有 ;
(0x3B),如果有的话,高位为 1 剩余都为 0
final long partialWord = word & ((mask >> 7) - 1);
这里的技巧是右移 7 位再减 1,等价于高位后 bytes 均为 1,那么这里就是分割 ;
后面 bytes 的值(这里是小端计算!!)
从上面的举例来说,也就是 101, 32, 67, 105, 116, 121, 59, 49
bytes 走这个逻辑:
64bits Long 值为 7286898317290176512L
也就是 0x6520436974790000
mask
值为 0x80000000000000
((mask >> 7) - 1)
值就是 0xFFFFFFFFFFFF
所以最后得到 7286898317290176512L
即 e City\000\000
后面还有一段代码, 也是一个技巧,由前文可知某一个 byte 是 0x80
,其余为 0,也就是说 0 的个数和 byte 的关系是 1:8
final int index = Long.numberOfTrailingZeros(mask) >> 3;
原文:https://lemire.me/blog/2022/01/21/swar-explained-parsing-eight-digits/
假设字符串是
12345678
转为小端的 bytes 是\x38 \x37 \x36 \x35 \x34 \x33 \x32 \x31
val -= 0x3030303030303030
则 val 的值为0x0807060504030201
(val * 10) + (val >> 8)
构造成 bytes 为10 * b1 + b2
(为了讨论的更为通用,采用原文形式 b1,b2,b3,b4,b5,b6,b7,b8)10 * b3 + b4
10 * b5 + b6
10 * b3 + b4
((val & mask) * mul1)
val & mask
只保留 1th, 5th byte* mul1
可以通过分配率的形式来理解,1th byte * 1000000ULL * 2^32
就是1th byte * 1000000ULL
, 通同理5th * 100
, 二者相加的和存放在 5th byte(这里还要注意这里可以存储 32 位,而这里最大也只有 255 * 10^6, 所以也防止溢出)(((val >> 16) & mask) * mul2)
同理,在 5th byte 上加上了(10 * b3 + b4) * 10000ULL + 10 * b7 + b8
最后第 5th byte 也就是 32 位开始的和就是
10^6*(10 * b1 + b2) + 10^2*(10 * b5 + b6) + 10^4*(10 * b3 + b4) + 10^0*(10 * b3 + b4)
也就是如下所示的累加和理解的过程中,把数值😢 :(1000000ULL
按照 10 进制的形式填到二进制里面,以为是0100 0000