琥珀春秋

昨天js课上讲到这样一个字符串填充函数，上课老师讲的不是多么仔细，没怎么听懂，下课后研究一下，问了一下以前教c的老师，发现这个小技巧还是很优秀的，可以很大程度的减少循环的次数，从而大大的减少运算的时间。

先看函数，随后我来解释思路：

//c:填充字符 length:长度
//getString(c,length)返回长度为length的字符串，它的所有字符均为c
function getString(c,length)
{
var bArr = length.toString(2).split(”");
// 将length转换成2进制数，并转换成数组
// 例如length为20，对应的2进制数是10100转换为数组bArr为["1","0","1","0","0"]
var ret = “”;
var step = c;// 初始步长为字符串c
for(var i = bArr.length-1;i>=0;i–)// 从末位开始连接字符串
{
if(bArr[i]==”1″) ret += step;// 当前位为1 时，在ret字符串后增加step
step += step;// 步长加倍
}
return ret;
}

function pad(str ,len ,c ,dir)
{
var out = String(str);// 原始字符串
if(!c) c = “0″;// 如果参数c未定义，则c取默认值“0”
if(!dir) dir = 1; // 如果参数dir未定义，则dir取默认值1
var pad = getString(c ,len – out.length); // 计算需要填充的字符串
if(dir > 0 ) out= pad + out; // 在左侧填充
else out += pad; // 在右侧填充
return out;
}
alert(pad(”aaaa”,8,”1″,1));//测试。

看完这个pad函数后，可以发现其最精华的部分在它调用getstring（）函数上，getstring()函数直接返回需要添加的字符串，并且添加的长度也是刚刚好。getstring()函数，最精华的部分在于将需要添加的字符串的长度直接转换成二进制的形式，并用数组保存每一个二进制位。
在分析这个循环之前，让我们先来想一下二进制数转换成十进制从低位到高位的运算。比如 二进制数10100 计算过程是 0*2^0 +0*2^1+1*2^2+0*2^3+1*2^4 = 20（十进制） ;
我们知道高一位的权值是低一位的权值的2倍，因此依次是2^0,2^1,2^2….
而我们的运算过程就是这一位的值与这一位的权值相乘的运算，随后各位的运算结果相加。而在getstring()函数中for循环的部分中，我们相当于做了一个根据二进制的值通过给定的字符来扩充字符串长度的操作。当bArr[i]==”1″，我们就要进位了，同时要增加”权值” ,当改为是0的时候，我们只是增加”权值”，就是通过step+=step来实现字符串长度的翻倍。
通过这样一个小技巧，可以很大程度的减少循环的次数，我们可以想象如果添加的字符串的长度是10000 的话，如果按照传统的一次增加一个字符的方式，要循环一万次，而通过这种方式，我们只需要将10000（十进制）转换成10011100010000（二进制），这样14次循环就可以计算出结果。
在此只是通过js来实现了这样一个算法，能够以此来加深对二进制操作的印象。

This entry was posted on 星期二, 09月 22nd, 2009 at 16:50 and is filed under 数据结构. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.