Re: question on the patch FastString

[云风 Cloud Wu <cloudwu@...>]

Philippe Verdy <verdyp@gmail.com> 于2020年5月26日周二 下午6:28写道：
>
> No, you've reduced the number of additions/substractions if you accept more groups of two bits. My solution with only groups of 1 bit has no solution for 32-bit words, but it has a solution for only 1 group of 2 bits.
>
> Think about multiplication by 0x011, it is the same as a multiplication by 0x100 and a subtraction of the input: 3*x = 4*x - x = (x<<2)-(x<<0).
>
I mean multiplication by 0x010101  =  16*x + 4*x + x,   = (x << 4) +
(x << 2) + (x << 0)    ,  2 additions
0x011011 == 31*x + 3*x = (32*x - 16*x) + (4*x - x)  = (x<<5) - (x<<4)
+ (x<<2) - (x<<0)  ,  1 addition and 2 subtractions

-- 
http://blog.codingnow.com