为了解决:“在1、2、3、......1000000这100W个连续自然数中任意删除2个,再把顺序打乱,请编码快速查找被删除的两个数”。采用JS异或运算如下:
<script type=text/javascript>
var i = 1000000, arr = [], m = n = "";
while (i --) {
arr.push(i + 1);
}
m = arr.splice(Math.random() * arr.length, 1);
n = arr.splice(Math.random() * arr.length, 1);
//------------------------------------------------
var t = new Date();
var x = 1000000,
j = k = arr.length,
q = w = l = 0;
while (j --) {
x ^= arr[j];
}
q = w = x;
while (! (q & 1)) {
q >>= 1,
l++;
}
while (k --) {
if (arr[k] >> l & 1) {
x ^= arr[k];
}
}
t = new Date() - t;
//------------------------------------------------
document.write("随机删除的两个数为:" + m + " 和 " + n + "<br/>");
document.write("找到被删的两个数为:" + x + " 和 " + [x ^ w] + "<br/>");
document.write("查找被删两数时间为:" + t + "毫秒");
</script>
为什么测试1000个以上连续自然数准确,而个数为100或者10会发生错误呢?
<script type=text/javascript>
var i = 1000000, arr = [], m = n = "";
while (i --) {
arr.push(i + 1);
}
m = arr.splice(Math.random() * arr.length, 1);
n = arr.splice(Math.random() * arr.length, 1);
//------------------------------------------------
var t = new Date();
var x = 1000000,
j = k = arr.length,
q = w = l = 0;
while (j --) {
x ^= arr[j];
}
q = w = x;
while (! (q & 1)) {
q >>= 1,
l++;
}
while (k --) {
if (arr[k] >> l & 1) {
x ^= arr[k];
}
}
t = new Date() - t;
//------------------------------------------------
document.write("随机删除的两个数为:" + m + " 和 " + n + "<br/>");
document.write("找到被删的两个数为:" + x + " 和 " + [x ^ w] + "<br/>");
document.write("查找被删两数时间为:" + t + "毫秒");
</script>
为什么测试1000个以上连续自然数准确,而个数为100或者10会发生错误呢?
var i = 1000000, arr = [], m = n = "";
while (i--) {
arr.push(i + 1);
}
m = arr.splice(Math.random() * arr.length, 1);
n = arr.splice(Math.random() * arr.length, 1);
//------------------------------------------------
var t = new Date();
var x = 1000000,
j = k = arr.length,
q = w = l = 0;
while (j--) {
x ^= arr[j];
}
q = w = x;
while (! (q & 1)) {
q >>= 1,
l++;
}
while (k--) {
if (arr[k] >> l & 1) {
x ^= arr[k];
}
}
t = new Date() - t;
//------------------------------------------------
document.write("随机抽取的两个数为:" + m + " 和 " + n + "<br/>");
document.write("找到抽取的两个数为:" + x + " 和 " + [x ^ w] + "<br/>");
document.write("查找时间为:" + t);
</script>
var i = 1000000, arr = [], m = n = "";
while (i --) {
arr.push(i + 1);
}
m = arr.splice(Math.random() * arr.length, 1);
n = arr.splice(Math.random() * arr.length, 1);
//------------------------------------------------
var t = new Date();
var x = 1000000, j = k = arr.length, q = w = l = 0;
while (j --) {
x ^= arr[j];
}
q = w = x;
while (! (q & 1)) {
q >>= 1,
l ++;
}
while (k --) {
if (arr[k] >> l & 1) {
x ^= arr[k];
}
}
t = new Date() - t;
//------------------------------------------------
document.write("随机抽取的两个数为:" + m + " 和 " + n + "<br>");
document.write("找到抽取的两个数为:" + x + " 和 " + [x ^ w] + "<br>");
document.write("查找时间为:" + t + "毫秒");
</script>
谢谢。
就算法而言,不应该出错的,这不仅仅就JS而言。
JS的位运算一定还有什么奥妙还未掌握,也许很简单,就像一层窗户纸,我猜。
var i = 1000000, arr = qrr = [], m = n = "";
while (i --) {
arr.push(i + 1);
}
qrr = arr.concat([]);
m = arr.splice(Math.random() * arr.length, 1);
n = arr.splice(Math.random() * arr.length, 1);
//------------------------------------------------
var t = new Date();
var x = 1000000, i = arr.length, j = qrr.length, q = w = l = 0;
while (i --) {
x ^= arr[i];
}
q = w = x;
while (!(q & 1)) {
q >>= 1, l ++;
}
while (j --) {
if (qrr[j] >> l & 1) {
x ^= qrr[j];
}
if (arr[j] >> l & 1) {
x ^= arr[j];
}
}
t = new Date() - t;
//------------------------------------------------
document.write("随机抽取的两个数为:" + m + " 和 " + n + "<br/>");
document.write("找到抽取的两个数为:" + x + " 和 " + [x ^ w] + "<br/>");
document.write("查找时间为:" + t);
</script>说明:x的初始值为连续整数间相互异或值,1-10个数的时候为11,1-100、1-1000...等等就等于最大的尾数,有代数式可一步求出来。我依然困惑的是,为什么错误的代码能够在大数量级的连续整数向量空间查找到正确的结果呢?
自然数1,2,3...n-1,n 求异或跟n相关。
switch(n%4){
case 0:return n;
case 1:return 1;
case 2:return n+1;
case 3:return 0;
}能在CSDN看到这样的代码,也难得。赞一个!
var i = 1000000, arr = qrr = [], m = n = "";
while (i --) {
arr.push(i + 1);
}
m = arr.splice(Math.random() * arr.length, 1);
n = arr.splice(Math.random() * arr.length, 1);
//------------------------------------------------
var t = new Date();
var x = y = q = l = k = 0, i = j = arr.length + 3;
while (i --) {
x ^= i ^ arr[i];
}
q = y = x;
while (! (q & 1)) {
q >>= 1, l ++;
}
while (j --) {
if (k = j >> l & 1) {
x ^= j;
}
if (arr[j] >> l & 1) {
x ^= arr[j];
}
}
t = new Date() - t;
//------------------------------------------------
document.write("随机抽取的两个数为:" + m + " 和 " + n + "<br/>");
document.write("找到抽取的两个数为:" + x + " 和 " + [x ^ y] + "<br/>");
document.write("查找时间为:" + t + "毫秒");
</script>