返回列表

Javascript位运算问题 |0,~

默认分类 2014/07/02 03:33

最近整理前端能力测试题目,翻到很久前去Intel面试问到位运算的问题|0,~,顺道整理了一下。

  1. 取整同时转成数值型: '10.567890'|0 结果: 10 '10.567890'^0 结果: 10 -2.23456789|0 结果: -2 ~~-2.23456789 结果: -2

  2. 日期转数值: var d = +new Date(); //1295698416792

  3. 类数组对象转数组: var arr = [].slice.call(arguments)

  4. 漂亮的随机码: Math.random().toString(16).substring(2); //14位 Math.random().toString(36).substring(2); //11位

  5. 合并数组: var a = [1,2,3]; var b = [4,5,6]; Array.prototype.push.apply(a, b); uneval(a); //[1,2,3,4,5,6]

  6. 用0补全位数: function prefixInteger(num, length) {   return (num / Math.pow(10, length)).toFixed(length).substr(2); }

  7. 交换值: a= [b, b=a][0];

  8. 将一个数组插入另一个数组的指定位置: var a = [1,2,3,7,8,9]; var b = [4,5,6]; var insertIndex = 3; a.splice.apply(a, Array.concat(insertIndex, 0, b)); // a: 1,2,3,4,5,6,7,8,9

  9. 删除数组元素: var a = [1,2,3,4,5]; a.splice(3,1);

  10. 快速取数组最大和最小值 Math.max.apply(Math, [1,2,3]) //3 Math.min.apply(Math, [1,2,3]) //1 (出自http://ejohn.org/blog/fast-javascript-maxmin/)

  11. 条件判断: var a = b && 1; 相当于 if (b) {   a = 1 }

var a = b || 1; 相当于 if (b) {   a = b; } else {   a = 1; }

  1. 判断IE: var ie = /@cc_on !@/false;

还有吗?欢迎回应

( function(){ } )();
->
( function(){}() );
->
+function(){}()
-function(){}()

前几日在网上看到一篇文章:[JavaScript绝句](http://site.douban.com/106371/widget/notes/22456/note/142716442/ "hehe"),看了以后觉得里面的代码颇为有趣,不过文章里面只是简单的说了这样写的目的和结果,却没有令读者起到既知其然,又知其所以然的效果。这里简单写一篇小文章剖析一下这篇“绝句”背后的原理吧。


1. 取整同时转成数值型

'10.567890'|0
//结果: 10
'10.567890'^0
//结果: 10
-2.23456789|0
//结果: -2
~~-2.23456789
//结果: -2

第一条绝句短短几句话,看起来十分的简洁,实际上背后的道理确是多了去了。这个东西分三大块:

结论:可用。利用了Javascript本身位运算自动取整的原理,至于位运算本身的效率比硬件处理速度低下……这个倒是无妨,因为我相信咱们自己写一个取整函数的效率应该也不会比Javascript自动取整高到哪儿去,多了个位运算这一点就忍了吧。

2. 日期转数值

var d = +new Date(); //1295698416792

这一段就写的不明不白的了,什么叫日期转数值?这应该叫日期转时间戳。查看MDN上的Date()对象,里面有这么一段话:

The JavaScript date is measured in milliseconds since midnight 01 January, 1970 UTC. A day holds 86,400,000 milliseconds. The JavaScript Date object range is -100,000,000 days to 100,000,000 days relative to 01 January, 1970 UTC.

意思就是说,JS本身时间的内部表示形式就是Unix时间戳,以毫秒为单位记录着当前距离1970年1月1日0点的时间单位。这里不过是用一元运算符 + 给他转换成本来的表示形式而已。至于一元运算符 + 的功能,就是把一个变量转化为数值型,并且不对其进行任何操作。MDN里对本操作符评价极高:

unary plus is the fastest and preferred way of converting something into a number, because it does not perform any other operations on the number.

结论:可用。是JS转化时间戳的一个好方法。

3. 类数组对象转数组

var arr = [].slice.call(arguments)

这里又是一个比较有趣的写法,所谓的“类数组”,这里指的是JS里面每个函数自带的内置对象 arguments ,其可以获得函数的参数,并以一种类似数组的方式来保存(实际上这个对象只有callee, caller, length的方法)。如果你要对数组进行诸如切片,连接等操作怎么办?你就可以用上面的这个方法,当然也是MDN给出的解决方案。

写到这里我恍然大悟啊,怪不得前几日写由JavaScript反柯里化所想到的时,大牛在操作arguments时,统统都是 Array.prototype.xxx.call(arguments, xxx, ...) ,原来原因很简单:arguments不是数组,木有这些方法;如果要用,请 callapply 之。

这里还有一个奇技淫巧:当你需要把 arguments 合并入一个数组时,你当然可以先用上面的方法转换然后 concat 之,你也可以利用 push 的原理直接用 push.apply,方法对比如下:

function test() {
    var res = ['item1', 'item2']
    res = res.concat(Array.prototype.slice.call(arguments)) //方法1
    Array.prototype.push.apply(res, arguments)              //方法2
}

我们可以清楚的看到,方法二比方法一短那么一点(喂!)。嗯,就是这样。

结论:可用。当然直接写[]会为内存增加垃圾,如果不怕绝句写的太长,还是可以写成上文 Array.prototype.push.apply 这种形式的。

4. 漂亮的随机码

Math.random().toString(16).substring(2);
Math.random().toString(36).substring(2);

这个十分好理解,生成一个随机数,转化为n进制,然后截取其中几位而已。其中 toString() 函数的参数为基底,范围为2~36。

结论:可用,但是位数是不确定的,为保险起见建议 toString(36).substring(2, 10) ,可以妥妥的截出八位来。

5. 合并数组:

var a = [1,2,3];
var b = [4,5,6];
Array.prototype.push.apply(a, b);
uneval(a); //[1,2,3,4,5,6]

好,这个东西其实非常的不错。在上文的奇技淫巧中我们也提到了,当b是类数组时,可以用 push 方法来进行数组合并。但这里的问题是……这个b根本就是数组啊喂!有什么必要啊,难道你觉得JS的 concat 还不够好用么?再次比较一下代码:

var a = [1,2,3]
var b = [4,5,6]
Array.prototype.push.apply(a, b)   //方法1
a = a.concat(b)                    //方法2

作者的方法长好多啊!然后那个自定义的函数uneval是个什么东西啊!JS木有这种函数啊!

结论:其实它正确的使用点在于3里面的奇技淫巧,对于单纯的数组……建议还是用concat吧。

6. 用0补全位数

function prefixInteger(num, length) {
    return (num / Math.pow(10, length)).toFixed(length).substr(2);
}
prefixInteger(2, 3)          //002

这里作者给我们展示了一个新的函数: toFixed(n) ,赶紧滚去查了一下MDN中的函数说明,这个函数的意思是对一个浮点数进行四舍五入,保留小数点后n位;默认为0,也即直接取整。

而作者这个函数的意思是把你给的一个数值先四舍五入取整,然后在前面补上各种0使最终获得一个等长的字符串。不过,由于他的算法是让原整数除以十的幂然后截取,这样当num的位数本身就多于length的时候就会出现bug,如下面这个输入:

prefixInteger(1234567, 3)     //34.567

最终输出的长度是5,不符合要求,所以函数应该进行错误处理之类的,比如加上下面这个 try catch 语句?

function prefixInteger(num, length) {
    try{
        if (num.toFixed().toString().length > length) 
            throw 'illegal number!'
        return (num / Math.pow(10, length)).toFixed(length).substr(2);
    }catch(err){
        console.log(err)
    }
}

结论:有点小bug,修改可用,不过改了以后蛮长的不像绝句像八股文呵呵其实我觉得还是可以再改进一点的。在某些场合的用处还是蛮强大的。

7. 交换值

a= [b, b=a][0];

本绝句中最帅的一句终于出场。这句话甚至有了pythonic的风格,虽然python的写法更简单:

a, b = b, a        #还是python最帅啊!

不过有豆瓣的网友对这一方法提出了质疑:交换值时声明的一个数组[b, b=a]产生了内存,只能等待JS自己进行内存回收。确实,如果要严格的节约内存,提高JS内存回收的效率,那么 new[]{}function 声明都应该少用(可以参照这篇文章:减少JavaScript垃圾回收)。不过至于交换变量,如果用传统的方式只能再声明一个变量做中介,这样实际上依旧会占用内存,不过这样内存是在函数完成时自动释放的罢了。

结论:可用,不过如果要批量使用,还是建议写个函数用函数内部变量交换。

8. 将一个数组插入另一个数组的指定位置

var a = [1,2,3,7,8,9];
var b = [4,5,6];
var insertIndex = 3;
a.splice.apply(a, Array.prototype.concat(insertIndex, 0, b));
// a: 1,2,3,4,5,6,7,8,9

这里用到了两个函数: spliceconcat ,我们看一下 splice 这个函数的定义arr.splice(x, y, item1, item2, ...) :就是从arr数组的第x位开始,首先削掉后面的y个,之后插入item1, item2等等。其实,这里是 apply 函数的一个通用应用:当函数foo的参数仅支持(item1, item2, ..)这样的参数传入时,如果你把item1, item2, ..存在数组items里,想把数组作为参数传给foo时,就可以这样写:

xx.foo.apply(xx, items)

结论:可用。鉴于 apply 函数可以把数组作为参数依次传入的性质,这只是广大应用中的一个特例。

9. 删除数组元素

var a = [1,2,3,4,5];
a.splice(3,1);           //a = [1,2,3,5]

是的,Javascript对于数组删除来说,没有什么好的方法。如果你用 delete a[3] 来删除的话,将会在数组里留下一个空洞,而且后面的下标也并没有递减。这个方法是道爷在书里提到的,原文如下:

Fortunately, JavaScript arrays have a splice method. It can do surgery on an array, deleting some number of elements and replacing them with other elements. The first argument is an ordinal in the array. The second argument is the number of elements to delete. (...) Because every property after the deleted property must be removed and reinserted with a new key, this might not go quickly for large arrays.

道爷说了这个函数的功能的同时也说了,这个函数实际上是把后面的元素先移除掉,然后作为新的键值重新插入,这样其实等于遍历了一次,和你自己写个for循环的效率差不多。而且道爷没有提到的是,这个函数是有一个返回值的,如果多次使用这样的函数操作,显然会增加内存的负担。所以或许从省内存的方式来看,使用for循环遍历然后逐个delete后面的元素会好一些。

结论:可用。既然道爷都推荐了,就不要纠结于这点可怜的内存上了吧。但是大型数组效率始终不高。

10. 快速取数组最大和最小值

Math.max.apply(Math, [1,2,3]) //3
Math.min.apply(Math, [1,2,3]) //1

这个就是重复绝句,详情参见绝句8。可能作者自己也不知道,apply一直是这么用的。

结论:可用,而且要学会这个技巧呀~

11. 条件判断:

var a = b && 1; 
//相当于
if (b) {
    a = 1
}

呵呵,这也算绝句呀……好吧。而且作者没有考虑到,如果b不为真,a的值就变成b了,也有豆瓣的网友看出了这个问题,其实这个应该相当于:

if (b) {
    a = 1
} else {
    a = b
}

结论:必须可用,没啥可说的。不过这是C语言里面的特性,不能算做是JavaScript的绝句吧。条件赋值如果不这么写你就out啦~

12. 判断IE:

var ie = /*@cc_on !@*/false;

好顶赞!当然不是说这个绝句好顶赞,而是我之前从来没有研究过如何判断IE,因为这个去看了一下,发现还是有很多方式的,列举如下:

// 貌似是最短的,利用IE不支持标准的ECMAscript中数组末逗号忽略的机制
var ie = !-[1,];
// 利用了IE的条件注释
var ie = /*@cc_on!@*/false;
// 还是条件注释
var ie//@cc_on=1;
// IE不支持垂直制表符
var ie = '\v'=='v';
// 原理同上
var ie = !+"\v1";

至于IE的条件注释,如果以后有精力再详细的补上吧。

结论:亲测可用,原理有待慢慢研究。

=====================================================================

小代码大学问之JavaScript位运算2014-03-27 09:23:31

这几天粗略的阅读了一下AngularJS的源码,在这个过程中发现有这么两段代码挺有意思的:

var manualLowercase = function(s) {
    return isString(s) ? s.replace(/[A-Z]/g, function(ch) {
        return String.fromCharCode(ch.charCodeAt(0) | 32);
    }) : s;
};
var manualUppercase = function(s) {
    return isString(s) ? s.replace(/[a-z]/g, function(ch) {
        return String.fromCharCode(ch.charCodeAt(0) & ~32);
    }) : s;
};

这两段代码用来处理字母大小写转换,由于某些国家(土耳其)使用toLowerCase()toUpperCase()不能正确的转换字母大小写,因而需要手动的处理。

为什么说这两段代码有意思?其实是觉得其中用位运算处理字母大小写的代码很巧妙,其核心代码如下:

ch.charCodeAt(0) | 32 // 大写转小写
ch.charCodeAt(0) & ~32  // 小写转大写

在分析两段代码之前,先来回顾一下JavaScript中的两个概念:整数位运算

从严格意义上讲,ECMAScript中有两种类型的整数:有符号的整数(正数和负数)和无符号的整数(只有正数)。而默认情况下JavaScript中的整数都是有符号的。

而在不考虑ECMAScript中数字格式存储与转换(为32位)的情况下,实际上我们操作的都是32位的整数。而对于上面提到的有符号整数而言,其中前31位(end<-start)表示数字的值,最后1位表示符号位(0表示正,1表示负)。

这里提到的32位的整数在计算机底层都是使用二进制格式存储的,而这个二进制由01组成,其中每一位都有对应的十进制数字结果,整个二进制数值代表的十进制结果由所有这些位对应的十进制数字之和。

这篇文章中不考虑负数的情况,一个32位二进制格式的数字看起来如下所示,这里以10为例:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0

二进制数字计算的方式:number ( Math.pow(2, index)),这里的number表示二进制中对应位上的数值0/1,index表示该数值在整个二进制格式的数字中的索引。注意一个二进制格式的起始点在右侧。

那么上面的数字就等于:`1 * Math.pow(2,3) + 1 * Math.pow(2, 1) = 10`。

前面提到了,这些二进制的数字实际上都是在计算机的底层完成的,而ECMAScript中刚好提供了二进制运算相关的操作符,这些操作符都是直接对运算数进行二进制操作的,并且都是发生在幕后的。

JavaScript中有7个位运算相关的运算符:

以上这些位运算符,最终操作的都是二进制数值。

在上面的代码中分别涉及到了按位非按位与按位或三种运算。先来针对上面的两段代码讲解一下这三个位运算符:

ch.charCodeAt(0) | 32

这段代码通过正则表达式匹配到给定字符串中的每个大写字母: A-Z;接下来使用字符串对象的charCodeAt()方法拿到该字符对应的Unicode编码,恰好这个编码是一个数字;最后使用按位或运算获取到另外一个数字。

为什么这里执行对数值32的按位或运算呢?当然这肯定不是空穴来风。那么我们先从大写字母及对应的Unicode值分析看看。不难发现,A-Z对应的Unicode编码分别为65-90;而这写编码对应的二进制表示分别为:1000001 ... 1011010。再看看小些字母对应的数据:其Unicode编码分别为:97-122,对应的二进制表示分别为:1100001...1111010。最后将它们放入一张表格中对比如下:

提示:使用(1).toString(2)便可以拿到每个数字对应的二进表示法的有效位。

大写字母二进制有效位 `1000001` ... `1011010`
小写字母二进制有效位 `1100001` ... `1111010`

在这个表格中没有完整列出每个字母对应的二进制有效位。但是通过完整的对比不难发现,大写字母与小写字母的二进制有效位都是7位,对这些数值进行对不不难发现大小写字母的二进制有效位中:大写字母的第6位0;而小写字母的第6位为1;而每个大小写自己的二进制有效位中刚好只有这一位不同。

因此我们在求值大写字母的对应的小写字母的二进制数值时转换大写字母的二进制数值第6位即可,其他的位是一样的不用转换。而第6位为1时,其对应的十进制数值刚好是32(1 * Math.pow(2, 5)),32对应的二进制数值的有效位为:100000

那么如何转换这里的第6位呢?我们的目的是将大写字母二进制数值第6位的0转换为1,而其他的位不变。最终我们只需要拿一个刚好第6位为1,其他位为0的二进制数值与大写字母的二进制数值进行位运算操作即可,这个能够用来进行有效位运算的二进制数值则为100000,而JavaScript中的按位或操作刚好能有做到这一点。

而在JavaScript中,我们并不能直接操作一个二进制的数值,二进制的运算都是在低层完成的,在JavaScript中这些都是按位运算符的使命。那么,在前面使用charCodeAt()方法已经拿到了大写字母对应的Unicode编码-即一个有效的十进制数字;而100000对应的十进制数字为32。

由此得出结论,使用大写字母对应的Unicode编码与32作按位或运算便能正确的拿到其对应的小写字母的Unicode编码,其操作过程如下:

以大写字母A为例

1 0 0 0 0 0 1
1 0 0 0 0 0
1 1 0 0 0 0 1

如此,便拿到了一个二进制数值:1100001,对应的十进制数字为97(parseInt('1100001', 2))。最后使用String对象的fromCharCode()方法得到的字符便是大写字母A对应的小写字母a

整个转换的过程中,所有的这些操作实际上都是在底层(?内存中)完成的。

上面剖析了大写字母转小写字母的过程。接下来再看看小写字母转大写字母。在上面的代码中,我们可以看到转大写字母的代码为:

ch.charCodeAt(0) & ~32

首先,同大写字母一样,使用字符串对象(String)的charCodeAt()方法拿到对应的Unicode编码(也是一个十进制数值)。在上面的字母二进制数值对比表格中我们已经找到了规律:即转换每个字母对应的二进制数值的第6即可。那么如何将小写字母的二进制数值的第6位1转换为0,而其位不变呢?

前面将大写字母的第6位0转位1,我们使用了按位或来保证将第6位正确的转换为1。而这一次小写转大写的过程中,我们必须保证正确的将第6位1转换为0,其他位不变即可。由此得出,这一次进行位运算的基本条件必须保证第二个操作数的第6位为0,而其他位该是1的是1,该是0的是0。

那么如何做到这一点呢?根据位运算的特点以及上面的分析,我们保证第6位不同即可,那么拿011111与小写字母的二进制数值进行按位与运算运算即可。而对32进行按位非运算的结果刚好为011111

以小写字母a为例

1 1 0 0 0 0 1
0 1 1 1 1 1
1 0 0 0 0 0 1

这里不一定必须是011111。比如拿一个完整的32位11111111111111111111111111011111也可以。但是在上述环境中,011111就能满足需求,而这个二进制数值对应的数值刚好是对32进行按位非的运算结果。

根据前面的分析,这样就拿到了大写字母A对应的二进制数值,再对它编码便可以返回最终的大写字母。

至此,对AngularJS中这两段代码的分析就完成了。也算是对JavaScript中的位运算做了一次巩固,温习。

其实JavaScript中的位运算远远不止这一点,我们还可以使用其他位运算符做到很多事情。下面是一些例子,不妨分析一下其运算原理:

// 获取0-max之间随机整数
function random(max) {
    return Math.random() * max | 0;
    // 获取 1-max之间的随机整数
    // return Math.random() * max | 1
}
// 奇偶判断
function isOdd(number) {
    return (parseInt(number) & 1) === 0;
}
function isEven(number) {
    return (parseInt(number) & 1) === 1;
}
// 取整
function int(number) {
    return number | 0;
}
// 取半
number >> 1;
// 2x
number << 1;
// 随机颜色
'#'+ ('000000' + (Math.random()*0xFFFFFF<<0).toString(16)).slice(-6);
// 还可以挖掘更多的技巧....

一些本文中用到的代码片段:

// 获取字符Unicode编码值
str.charCodeAt(0);
// 获取字符二进制数值有效位
str.charCodeAt(0).toString(2);
// 解析二进制数值
parseInt(binaryNumber, 2);
// 解析Unicode数值位对应的字符
String.fromCharCode(unicodeNumber);

写在最后,虽然代码很小,但是其中学问还是蛮大的,仔细分析一下感觉收获很多。在这里尤其感谢我的导师@toobug不厌其烦的在KFC给我讲解了很多基础知识,我还可耻的让他请我喝了一杯可乐,嗯,我很性福有木有。

参考资料