问题

给定一个以二进制编码的数字，以字符串形式呈现。如果是偶数，做除2操作；奇数做减1操作。如此往复操作，直到最后变成0，统计操作的次数
例如28 :‘11100’
第1次操作 28/2=14 1110
第2次操作 14/2=7 111
第3次操作 7-1=6 110
第4次操作 6/2=3 11
第5次操作 3-1=2 10
第6次操作 2/2=1 1
第7次操作 1-1=0 0

分析与解答

本题目看起来是一个计算题目，实际上隐含了很多有关二进制的计算细节。最初，我的计算是按照给定计算规则进行的，

第1种，暴力直接解题方法如下

package solution

// you can also use imports, for example:
// import "fmt"
// import "os"
import (
	"strconv"
)

// Solution soultion
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(S string) int {
	var cnt int
	num, _ := strconv.ParseInt(S, 2, 0)
	for num > 0 {
		var tmp int64
		if num%2 == 0 {
			tmp = num / 2
		} else {
			tmp = num - 1
		}
		num = tmp
		cnt++
	}

	return cnt
}

这种解决方法存在无法解决超大数的问题，主要原因在于它依赖于strconv.ParseInt()方法提供的转换精度，对于像4000个1组成的二进制字符串，完全无法计算。

第2种方法，通过对字符比特化解决

其主要依赖于把传入字符串参数S转换为byte数组

bnums := []byte(S)

然后从字符串末端开始，逢1替换为0，逢0直接去掉最末的元素

// Solution soultion
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(S string) int {
    length := len(S)
    var cnt int
    bnums := []byte(S)
    length = len(bnums)
    var b0, b1 byte = 48, 49
    for i := 0; i < length; i++ {
        if bnums[i] == b0 {
            bnums = bnums[i+1:]
            length--
            i--
        } else {
            break
        }
    }
   
    for length > 0 {
        if bnums[length-1] == b1 {
            bnums[length-1] = b0
        } else {
            bnums = bnums[:length-1]
            length--
        }
        if len(bnums) == 0 {
            break
        }
        cnt++
    }
    return cnt
}

尽管byte化方法解决了超大数的问题，但是仍然存在对golang列表切片的操作，这样不免有额外的内存开销，所以只能算是勉强解决问题。

第3种方法，直接对字符串种的1计数来解决

通过对题目二进制缩减规则观察，我们可以找到一个规律:

  • 字符串长度大于2的情况下，对于末位是1的操作减少1位，其需要操作2次，譬如: 111(7)-> 110(6)->11(3)

  • 对于末位是0的操作减少1位，其操作需要1次，譬如 110(6)->11(3)

  • 对于最后一个1其变化位0截至操作，其操作次数为1

    总结该规律，我们可以通过对传入二进制参数的字符串长度，结合统计其中1的个数，就可以计算得知需要操作的次数。

//Solution imporved solution
func Solution(S string) int {
    S = regexp.MustCompile(`^[0]+`).ReplaceAllString(S, "")
 
    var cnt int
    for _, chr := range S {
        if chr == '1' {
            cnt++
        }
    }
    return len(S) + cnt - 1
}

总结

这是一家大厂的面试题目之一，尽管看起来简单，考察的知识点却很全面，临考时候本人也只想到了一和二，但是当时提供的方案二还存在瑕疵。对于文中提供的3种方法种，第一种最直接容易，第二种需要我们对ASCII码种0和1的计数有所了解，第三种方法使用了正则表达式，主要是为了防止传入二进制数字的字符串前面带有很多0，这样会使得最后的结果不准确。

参考