精华内容
下载资源
问答
  • 快速判断二进制中有几个1 方法1: 这里涉及一个&的知识点,&是按位与,就是在一位一位的做与运算, while(n>0) //这一句,当n不等于0的时候循环执行以下循环体,n等于0的变化条件在n>>=1这一句,...

    大佬们常用的无穷大量:
    const int inf = 0x3f3f3f3f;

    快速判断二进制中有几个1

    方法1:
    
    这里涉及一个&的知识点,&是按位与,就是在一位一位的做与运算,
    while(n>0) //这一句,当n不等于0的时候循环执行以下循环体,n等于0的变化条件在n>>=1这一句,将n左移一位,这样当n中所有的”1”位都移出时,就跳出循环了
    {
    if((n&1)==1) //这句逐个通过位与的方式查看当前n最左边的一位是不是1,若是,则n&1=1,c加1用来计数
    c++;
    n>>=1;
    }
    return c;//这样循环结束时就能得到所需的1的个数了
    需要注意的是循环条件这部分很巧妙,保证当n的右边没有1的时候就不做循环了,可以假设n=1,循环体就只执行一次就跳出了,而不用遍历n的每一位
    
    方法2:
    
    x=x&(x-1)
    
    表达式的意思就是:把x的二进制表示 从低位开始,将遇到的第一个为1的比特位 置0。
    
    例如:
    
    e1:
    x = 01001000
    x-1 = 01000111
    x&(x-1)=01000000
    
    e2:
    x = 01001001
    x-1 = 01001000
    x&(x-1)=01001000
    
    在循环中利用该表达式可以快速的判断一个数的二进制中有多少个1int func(x)
    {
    int countx = 0;
    while(x)
    {
    countx ++;
    x = x&(x-1);
    }
    return countx;
    }
    
    x=x&(x-1)还可以快速判断x是不是2^n。当x为unsigned类型的变量,且其值为2的n次幂的时候,结果为零
    

    快速幂取模(防止爆ll)

    LL mul(LL a,LL b)
    {
        LL ans=0;
        while(b)
        {
            if(b&1) ans=(ans+a)%p;
            a=(a+a)%p;
            b=b>>1;
        }
        return ans;
    }
    LL Pow(LL a,LL b)
    {
        LL result=1;
        LL base=a%p;
        while(b)
        {
            if(b&1) result=mul(result,base)%p;
            base=mul(base,base)%p;
            b=b>>1;
        }
        return result;
    }
    

    参考文章:
    https://blog.csdn.net/si444555666777/article/details/82253837?ops_request_misc=%25257B%252522request%25255Fid%252522%25253A%252522161287323116780261962447%252522%25252C%252522scm%252522%25253A%25252220140713.130102334.pc%25255Fall.%252522%25257D&request_id=161287323116780261962447&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2allfirst_rank_v2~rank_v29-1-82253837.pc_search_result_cache&utm_term=%25E4%25BA%258C%25E8%25BF%259B%25E5%2588%25B6%25E6%2580%258E%25E4%25B9%2588%25E5%25BF%25AB%25E9%2580%259F%25E5%2588%25A4%25E6%2596%25AD%25E4%25B8%2580%25E4%25B8%25AA%25E6%2595%25B0%25E9%2587%258C%25E6%259C%2589%25E5%2587%25A0%25E4%25B8%25AA%25E4%25B8%2580

    展开全文
  • 二进制代码植入工具

    千次阅读 2007-08-17 18:52:00
    静态植入是通过二进制代码重写来实现的,植入时不允许代码;动态植入是在被植入代码运行过程中,通过一个小的虚拟机在特定时刻执行待植入代码来实现植入。A. Static instrumentation tools1. ATOM2. DTools ...

    对二进制的代码植入分为两类,静态植入和动态植入。静态植入是通过二进制代码重写来实现的,植入时不允许代码;动态植入是在被植入代码运行过程中,通过一个小的虚拟机在特定时刻执行待植入代码来实现植入。

    A. Static instrumentation tools

    1. ATOM

    2. DTools (http://research.microsoft.com/sn/detours/)

    B. Dynamic instrumentation tools

    1. Pin (http://rogue.colorado.edu/Pin/)

    2. DynamoRIO (http://www.cag.lcs.mit.edu/dynamorio/)

    3. Valgrind (http://www.valgrind.org/

    展开全文
  • JavaScript-二进制二进制数组

    万次阅读 2016-07-03 18:09:40
    但是,当我想处理文件的传输时候,使用二进制进行传输可以更快。在进行异步数据传输(AJAX)时,很可能出现这种场景。BlobBlob(Binary Large Object)对象代表了一段二进制数据,提供了一系列操作接口。其他

    在ES5中引入了Blob用于处理二进制。在ES6中引入了ArrayBuffer、TypedArray、DataView用于处理二进制数组。常规的前端操作用,用到二进制的地方不多。但是,当我想处理文件的传输时候,使用二进制进行传输可以更快。在进行异步数据传输(AJAX)时,很可能出现这种场景。

    Blob

    Blob(Binary Large Object)对象代表了一段二进制数据,提供了一系列操作接口。其他操作二进制数据的API(比如File对象),都是建立在Blob对象基础上的,继承了它的属性和方法。

    生成Blob对象有两种方法:一种是使用Blob构造函数,另一种是对现有的Blob对象使用slice方法切出一部分。

    (1)Blob构造函数,接受两个参数。第一个参数是一个包含实际数据的数组,第二个参数是数据的类型,这两个参数都不是必需的。

    var htmlParts = ["<a id=\"a\"><b id=\"b\">hey!<\/b><\/a>"];
    var myBlob = new Blob(htmlParts, { "type" : "text\/xml" });

    下面是一个利用Blob对象,生成可下载文件的例子。

    var blob = new Blob(["Hello Lee"]);
    
    var a = document.createElement("a");
    a.href = window.URL.createObjectURL(blob);
    a.download = "hello-lee.txt";
    a.textContent = "Download Hello World!";
    
    body.appendChild(a);

    上面的代码生成了一个超级链接,点击后提示下载文本文件hello-lee.txt,文件内容为“Hello Lee”。

    (2)Blob对象的slice方法,将二进制数据按照字节分块,返回一个新的Blob对象。

    var newBlob = oldBlob.slice(startingByte, endindByte);

    下面是一个使用XMLHttpRequest对象,将大文件分割上传的例子。

    function upload(blobOrFile) {
      var xhr = new XMLHttpRequest();
      xhr.open('POST', '/server', true);
      xhr.onload = function(e) { ... };
      xhr.send(blobOrFile);
    }
    
    document.querySelector('input[type="file"]').addEventListener('change', function(e) {
      var blob = this.files[0];
    
      const BYTES_PER_CHUNK = 1024 * 1024; // 1MB chunk sizes.
      const SIZE = blob.size;
    
      var start = 0;
      var end = BYTES_PER_CHUNK;
    
      while(start < SIZE) {
        upload(blob.slice(start, end));
    
        start = end;
        end = start + BYTES_PER_CHUNK;
      }
    }, false);
    
    })();

    (3)Blob对象有两个只读属性:

    • size:二进制数据的大小,单位为字节。
    • type:二进制数据的MIME类型,全部为小写,如果类型未知,则该值为空字符串。
      在Ajax操作中,如果xhr.responseType设为blob,接收的就是二进制数据。

    二进制数组

    (1)ArrayBuffer对象:代表内存之中的一段二进制数据,可以通过“视图”进行操作。“视图”部署了数组接口,这意味着,可以用数组的方法操作内存。

    (2) TypedArray对象:用来生成内存的视图,通过9个构造函数,可以生成9种数据格式的视图,比如Uint8Array(无符号8位整数)数组视图, Int16Array(16位整数)数组视图, Float32Array(32位浮点数)数组视图等等。

    (3)DataView对象:用来生成内存的视图,可以自定义格式和字节序,比如第一个字节是Uint8(无符号8位整数)、第二个字节是Int16(16位整数)、第三个字节是Float32(32位浮点数)等等。

    简单说,ArrayBuffer对象代表原始的二进制数据,TypedArray对象代表确定类型的二进制数据,DataView对象代表不确定类型的二进制数据。它们支持的数据类型一共有9种(DataView对象支持除Uint8C以外的其他8种)。

    ArrayBuffe对象

    概述

    ArrayBuffer对象代表储存二进制数据的一段内存,它不能直接读写,只能通过视图(TypedArray视图和DataView视图)来读写,视图的作用是以指定格式解读二进制数据。

    ArrayBuffer也是一个构造函数,可以分配一段可以存放数据的连续内存区域。

    var buf = new ArrayBuffer(32);

    上面代码生成了一段32字节的内存区域,每个字节的值默认都是0。可以看到,ArrayBuffer构造函数的参数是所需要的内存大小(单位字节)。

    为了读写这段内容,需要为它指定视图。DataView视图的创建,需要提供ArrayBuffer对象实例作为参数。

    var buf = new ArrayBuffer(32);
    var dataView = new DataView(buf);
    dataView.getUint8(0) // 0

    上面代码对一段32字节的内存,建立DataView视图,然后以不带符号的8位整数格式,读取第一个元素,结果得到0,因为原始内存的ArrayBuffer对象,默认所有位都是0。

    另一种TypedArray视图,与DataView视图的一个区别是,它不是一个构造函数,而是一组构造函数,代表不同的数据格式。

    var buffer = new ArrayBuffer(12);
    
    var x1 = new Int32Array(buffer);
    x1[0] = 1;
    var x2 = new Uint8Array(buffer);
    x2[0]  = 2;
    
    x1[0] // 2

    上面代码对同一段内存,分别建立两种视图:32位带符号整数(Int32Array构造函数)和8位不带符号整数(Uint8Array构造函数)。由于两个视图对应的是同一段内存,一个视图修改底层内存,会影响到另一个视图。

    TypedArray视图的构造函数,除了接受ArrayBuffer实例作为参数,还可以接受正常数组作为参数,直接分配内存生成底层的ArrayBuffer实例,并同时完成对这段内存的赋值。

    var typedArray = new Uint8Array([0,1,2]);
    typedArray.length // 3
    
    typedArray[0] = 5;
    typedArray // [5, 1, 2]

    上面代码使用TypedArray视图的Uint8Array构造函数,新建一个不带符号的8位整数视图。可以看到,Uint8Array直接使用正常数组作为参数,对底层内存的赋值同时完成。

    ArrayBuffer.prototype.byteLength

    ArrayBuffer实例的byteLength属性,返回所分配的内存区域的字节长度。

    var buffer = new ArrayBuffer(32);
    buffer.byteLength
    // 32

    如果要分配的内存区域很大,有可能分配失败(因为没有那么多的连续空余内存),所以有必要检查是否分配成功。

    if (buffer.byteLength === n) {
      // 成功
    } else {
      // 失败
    }

    ArrayBuffer.prototype.slice()

    ArrayBuffer实例有一个slice方法,允许将内存区域的一部分,拷贝生成一个新的ArrayBuffer对象。

    var buffer = new ArrayBuffer(8);
    var newBuffer = buffer.slice(0, 3);

    上面代码拷贝buffer对象的前3个字节(从0开始,到第3个字节前面结束),生成一个新的ArrayBuffer对象。slice方法其实包含两步,第一步是先分配一段新内存,第二步是将原来那个ArrayBuffer对象拷贝过去。

    slice方法接受两个参数,第一个参数表示拷贝开始的字节序号(含该字节),第二个参数表示拷贝截止的字节序号(不含该字节)。如果省略第二个参数,则默认到原ArrayBuffer对象的结尾。

    除了slice方法,ArrayBuffer对象不提供任何直接读写内存的方法,只允许在其上方建立视图,然后通过视图读写。

    ArrayBuffer.isView()

    ArrayBuffer有一个静态方法isView,返回一个布尔值,表示参数是否为ArrayBuffer的视图实例。这个方法大致相当于判断参数,是否为TypedArray实例或DataView实例。

    var buffer = new ArrayBuffer(8);
    ArrayBuffer.isView(buffer) // false
    
    var v = new Int32Array(buffer);
    ArrayBuffer.isView(v) // true

    TypedArray对象

    概述

    ArrayBuffer对象作为内存区域,可以存放多种类型的数据。同一段内存,不同数据有不同的解读方式,这就叫做“视图”(view)。ArrayBuffer有两种视图,一种是TypedArray视图,另一种是DataView视图,两者的区别主要是字节序,前者的数组成员都是同一个数据类型,后者的数组成员可以是不同的数据类型。

    目前,TypedArray对象一共提供9种类型的视图,每一种视图都是一种构造函数。

    Int8Array:8位有符号整数,长度1个字节。
    Uint8Array:8位无符号整数,长度1个字节。
    Uint8ClampedArray:8位无符号整数,长度1个字节,溢出处理不同。
    Int16Array:16位有符号整数,长度2个字节。
    Uint16Array:16位无符号整数,长度2个字节。
    Int32Array:32位有符号整数,长度4个字节。
    Uint32Array:32位无符号整数,长度4个字节。
    Float32Array:32位浮点数,长度4个字节。
    Float64Array:64位浮点数,长度8个字节。

    这9个构造函数生成的对象,统称为TypedArray对象。它们很像正常数组,都有length属性,都能用方括号运算符([])获取单个元素,所有数组的方法,在类型化数组上面都能使用。两者的差异主要在以下方面。

    TypedArray数组的所有成员,都是同一种类型和格式。
    TypedArray数组的成员是连续的,不会有空位。
    Typed化数组成员的默认值为0。比如,new Array(10)返回一个正常数组,里面没有任何成员,只是10个空位;new Uint8Array(10)返回一个类型化数组,里面10个成员都是0。
    TypedArray数组只是一层视图,本身不储存数据,它的数据都储存在底层的ArrayBuffer对象之中,要获取底层对象必须使用buffer属性。

    构造函数

    TypedArray数组提供9种构造函数,用来生成相应类型的数组实例。

    构造函数有多种用法。

    (1)TypedArray(buffer, byteOffset=0, length?)

    同一个ArrayBuffer对象之上,可以根据不同的数据类型,建立多个视图。

    // 创建一个8字节的ArrayBuffer
    var b = new ArrayBuffer(8);
    
    // 创建一个指向b的Int32视图,开始于字节0,直到缓冲区的末尾
    var v1 = new Int32Array(b);
    
    // 创建一个指向b的Uint8视图,开始于字节2,直到缓冲区的末尾
    var v2 = new Uint8Array(b, 2);
    
    // 创建一个指向b的Int16视图,开始于字节2,长度为2
    var v3 = new Int16Array(b, 2, 2);

    上面代码在一段长度为8个字节的内存(b)之上,生成了三个视图:v1、v2和v3。

    视图的构造函数可以接受三个参数:

    第一个参数(必需):视图对应的底层ArrayBuffer对象。
    第二个参数(可选):视图开始的字节序号,默认从0开始。
    第三个参数(可选):视图包含的数据个数,默认直到本段内存区域结束。
    因此,v1、v2和v3是重叠的:v1[0]是一个32位整数,指向字节0~字节3;v2[0]是一个8位无符号整数,指向字节2;v3[0]是一个16位整数,指向字节2~字节3。只要任何一个视图对内存有所修改,就会在另外两个视图上反应出来。

    注意,byteOffset必须与所要建立的数据类型一致,否则会报错。

    var buffer = new ArrayBuffer(8);
    var i16 = new Int16Array(buffer, 1);
    // Uncaught RangeError: start offset of Int16Array should be a multiple of 2

    上面代码中,新生成一个8个字节的ArrayBuffer对象,然后在这个对象的第一个字节,建立带符号的16位整数视图,结果报错。因为,带符号的16位整数需要两个字节,所以byteOffset参数必须能够被2整除。

    如果想从任意字节开始解读ArrayBuffer对象,必须使用DataView视图,因为TypedArray视图只提供9种固定的解读格式。

    (2)TypedArray(length)

    视图还可以不通过ArrayBuffer对象,直接分配内存而生成。

    var f64a = new Float64Array(8);
    f64a[0] = 10;
    f64a[1] = 20;
    f64a[2] = f64a[0] + f64a[1];

    上面代码生成一个8个成员的Float64Array数组(共64字节),然后依次对每个成员赋值。这时,视图构造函数的参数就是成员的个数。可以看到,视图数组的赋值操作与普通数组的操作毫无两样。

    (3)TypedArray(typedArray)

    类型化数组的构造函数,可以接受另一个视图实例作为参数。

    var typedArray = new Int8Array(new Uint8Array(4));

    上面代码中,Int8Array构造函数接受一个Uint8Array实例作为参数。

    注意,此时生成的新数组,只是复制了参数数组的值,对应的底层内存是不一样的。新数组会开辟一段新的内存储存数据,不会在原数组的内存之上建立视图。

    var x = new Int8Array([1, 1]);
    var y = new Int8Array(x);
    x[0] // 1
    y[0] // 1
    
    x[0] = 2;
    y[0] // 1

    上面代码中,数组y是以数组x为模板而生成的,当x变动的时候,y并没有变动。

    如果想基于同一段内存,构造不同的视图,可以采用下面的写法。

    var x = new Int8Array([1, 1]);
    var y = new Int8Array(x.buffer);
    x[0] // 1
    y[0] // 1
    
    x[0] = 2;
    y[0] // 2

    (4)TypedArray(arrayLikeObject)

    构造函数的参数也可以是一个普通数组,然后直接生成TypedArray实例。

    var typedArray = new Uint8Array([1, 2, 3, 4]);
    注意,这时TypedArray视图会重新开辟内存,不会在原数组的内存上建立视图。

    上面代码从一个普通的数组,生成一个8位无符号整数的TypedArray实例。

    TypedArray数组也可以转换回普通数组。

    var normalArray = Array.prototype.slice.call(typedArray);

    数组方法

    普通数组的操作方法和属性,对TypedArray数组完全适用。

    TypedArray.prototype.copyWithin(target, start[, end = this.length])
    TypedArray.prototype.entries()
    TypedArray.prototype.every(callbackfn, thisArg?)
    TypedArray.prototype.fill(value, start=0, end=this.length)
    TypedArray.prototype.filter(callbackfn, thisArg?)
    TypedArray.prototype.find(predicate, thisArg?)
    TypedArray.prototype.findIndex(predicate, thisArg?)
    TypedArray.prototype.forEach(callbackfn, thisArg?)
    TypedArray.prototype.indexOf(searchElement, fromIndex=0)
    TypedArray.prototype.join(separator)
    TypedArray.prototype.keys()
    TypedArray.prototype.lastIndexOf(searchElement, fromIndex?)
    TypedArray.prototype.map(callbackfn, thisArg?)
    TypedArray.prototype.reduce(callbackfn, initialValue?)
    TypedArray.prototype.reduceRight(callbackfn, initialValue?)
    TypedArray.prototype.reverse()
    TypedArray.prototype.slice(start=0, end=this.length)
    TypedArray.prototype.some(callbackfn, thisArg?)
    TypedArray.prototype.sort(comparefn)
    TypedArray.prototype.toLocaleString(reserved1?, reserved2?)
    TypedArray.prototype.toString()
    TypedArray.prototype.values()
    上面所有方法的用法,请参阅数组方法的介绍,这里不再重复了。

    另外,TypedArray数组与普通数组一样,部署了Iterator接口,所以可以被遍历。

    let ui8 = Uint8Array.of(0, 1, 2);
    for (let byte of ui8) {
      console.log(byte);
    }
    // 0
    // 1
    // 2

    字节序

    字节序指的是数值在内存中的表示方式。

    var buffer = new ArrayBuffer(16);
    var int32View = new Int32Array(buffer);
    
    for (var i = 0; i < int32View.length; i++) {
      int32View[i] = i * 2;
    }

    上面代码生成一个16字节的ArrayBuffer对象,然后在它的基础上,建立了一个32位整数的视图。由于每个32位整数占据4个字节,所以一共可以写入4个整数,依次为0,2,4,6。

    如果在这段数据上接着建立一个16位整数的视图,则可以读出完全不一样的结果。

    var int16View = new Int16Array(buffer);
    
    for (var i = 0; i < int16View.length; i++) {
      console.log("Entry " + i + ": " + int16View[i]);
    }
    // Entry 0: 0
    // Entry 1: 0
    // Entry 2: 2
    // Entry 3: 0
    // Entry 4: 4
    // Entry 5: 0
    // Entry 6: 6
    // Entry 7: 0

    由于每个16位整数占据2个字节,所以整个ArrayBuffer对象现在分成8段。然后,由于x86体系的计算机都采用小端字节序(little endian),相对重要的字节排在后面的内存地址,相对不重要字节排在前面的内存地址,所以就得到了上面的结果。

    比如,一个占据四个字节的16进制数0x12345678,决定其大小的最重要的字节是“12”,最不重要的是“78”。小端字节序将最不重要的字节排在前面,储存顺序就是78563412;大端字节序则完全相反,将最重要的字节排在前面,储存顺序就是12345678。目前,所有个人电脑几乎都是小端字节序,所以TypedArray数组内部也采用小端字节序读写数据,或者更准确的说,按照本机操作系统设定的字节序读写数据。

    这并不意味大端字节序不重要,事实上,很多网络设备和特定的操作系统采用的是大端字节序。这就带来一个严重的问题:如果一段数据是大端字节序,TypedArray数组将无法正确解析,因为它只能处理小端字节序!为了解决这个问题,JavaScript引入DataView对象,可以设定字节序,下文会详细介绍。

    下面是另一个例子。

    // 假定某段buffer包含如下字节 [0x02, 0x01, 0x03, 0x07]
    var buffer = new ArrayBuffer(4);
    var v1 = new Uint8Array(buffer);
    v1[0] = 2;
    v1[1] = 1;
    v1[2] = 3;
    v1[3] = 7;
    
    var uInt16View = new Uint16Array(buffer);
    
    // 计算机采用小端字节序
    // 所以头两个字节等于258
    if (uInt16View[0] === 258) {
      console.log('OK'); // "OK"
    }
    
    // 赋值运算
    uInt16View[0] = 255;    // 字节变为[0xFF, 0x00, 0x03, 0x07]
    uInt16View[0] = 0xff05; // 字节变为[0x05, 0xFF, 0x03, 0x07]
    uInt16View[1] = 0x0210; // 字节变为[0x05, 0xFF, 0x10, 0x02]

    下面的函数可以用来判断,当前视图是小端字节序,还是大端字节序。

    const BIG_ENDIAN = Symbol('BIG_ENDIAN');
    const LITTLE_ENDIAN = Symbol('LITTLE_ENDIAN');
    
    function getPlatformEndianness() {
      let arr32 = Uint32Array.of(0x12345678);
      let arr8 = new Uint8Array(arr32.buffer);
      switch ((arr8[0]*0x1000000) + (arr8[1]*0x10000) + (arr8[2]*0x100) + (arr8[3])) {
        case 0x12345678:
          return BIG_ENDIAN;
        case 0x78563412:
          return LITTLE_ENDIAN;
        default:
          throw new Error('Unknown endianness');
      }
    }

    总之,与普通数组相比,TypedArray数组的最大优点就是可以直接操作内存,不需要数据类型转换,所以速度快得多。

    BYTES_PER_ELEMENT属性

    每一种视图的构造函数,都有一个BYTES_PER_ELEMENT属性,表示这种数据类型占据的字节数。

    Int8Array.BYTES_PER_ELEMENT // 1
    Uint8Array.BYTES_PER_ELEMENT // 1
    Int16Array.BYTES_PER_ELEMENT // 2
    Uint16Array.BYTES_PER_ELEMENT // 2
    Int32Array.BYTES_PER_ELEMENT // 4
    Uint32Array.BYTES_PER_ELEMENT // 4
    Float32Array.BYTES_PER_ELEMENT // 4
    Float64Array.BYTES_PER_ELEMENT // 8
    这个属性在TypedArray实例上也能获取,即有TypedArray.prototype.BYTES_PER_ELEMENT。

    ArrayBuffer与字符串的互相转换

    ArrayBuffer转为字符串,或者字符串转为ArrayBuffer,有一个前提,即字符串的编码方法是确定的。假定字符串采用UTF-16编码(JavaScript的内部编码方式),可以自己编写转换函数。

    // ArrayBuffer转为字符串,参数为ArrayBuffer对象
    function ab2str(buf) {
      return String.fromCharCode.apply(null, new Uint16Array(buf));
    }
    
    // 字符串转为ArrayBuffer对象,参数为字符串
    function str2ab(str) {
      var buf = new ArrayBuffer(str.length * 2); // 每个字符占用2个字节
      var bufView = new Uint16Array(buf);
      for (var i = 0, strLen = str.length; i < strLen; i++) {
        bufView[i] = str.charCodeAt(i);
      }
      return buf;
    }

    溢出

    不同的视图类型,所能容纳的数值范围是确定的。超出这个范围,就会出现溢出。比如,8位视图只能容纳一个8位的二进制值,如果放入一个9位的值,就会溢出。

    TypedArray数组的溢出处理规则,简单来说,就是抛弃溢出的位,然后按照视图类型进行解释。

    var uint8 = new Uint8Array(1);
    
    uint8[0] = 256;
    uint8[0] // 0
    
    uint8[0] = -1;
    uint8[0] // 255

    上面代码中,uint8是一个8位视图,而256的二进制形式是一个9位的值100000000,这时就会发生溢出。根据规则,只会保留后8位,即00000000。uint8视图的解释规则是无符号的8位整数,所以00000000就是0。

    负数在计算机内部采用“2的补码”表示,也就是说,将对应的正数值进行否运算,然后加1。比如,-1对应的正值是1,进行否运算以后,得到11111110,再加上1就是补码形式11111111。uint8按照无符号的8位整数解释11111111,返回结果就是255。

    一个简单转换规则,可以这样表示。

    正向溢出(overflow):当输入值大于当前数据类型的最大值,结果等于当前数据类型的最小值加上余值,再减去1。
    负向溢出(underflow):当输入值小于当前数据类型的最小值,结果等于当前数据类型的最大值减去余值,再加上1。
    请看下面的例子。

    var int8 = new Int8Array(1);
    
    int8[0] = 128;
    int8[0] // -128
    
    int8[0] = -129;
    int8[0] // 127

    上面例子中,int8是一个带符号的8位整数视图,它的最大值是127,最小值是-128。输入值为128时,相当于正向溢出1,根据“最小值加上余值,再减去1”的规则,就会返回-128;输入值为-129时,相当于负向溢出1,根据“最大值减去余值,再加上1”的规则,就会返回127。

    Uint8ClampedArray视图的溢出规则,与上面的规则不同。它规定,凡是发生正向溢出,该值一律等于当前数据类型的最大值,即255;如果发生负向溢出,该值一律等于当前数据类型的最小值,即0。

    var uint8c = new Uint8ClampedArray(1);
    
    uint8c[0] = 256;
    uint8c[0] // 255
    
    uint8c[0] = -1;
    uint8c[0] // 0

    上面例子中,uint8C是一个Uint8ClampedArray视图,正向溢出时都返回255,负向溢出都返回0。

    TypedArray.prototype.buffer

    TypedArray实例的buffer属性,返回整段内存区域对应的ArrayBuffer对象。该属性为只读属性。

    var a = new Float32Array(64);
    var b = new Uint8Array(a.buffer);

    上面代码的a视图对象和b视图对象,对应同一个ArrayBuffer对象,即同一段内存。

    TypedArray.prototype.byteLength,TypedArray.prototype.byteOffset
    byteLength属性返回TypedArray数组占据的内存长度,单位为字节。byteOffset属性返回TypedArray数组从底层ArrayBuffer对象的哪个字节开始。这两个属性都是只读属性。

    var b = new ArrayBuffer(8);
    
    var v1 = new Int32Array(b);
    var v2 = new Uint8Array(b, 2);
    var v3 = new Int16Array(b, 2, 2);
    
    v1.byteLength // 8
    v2.byteLength // 6
    v3.byteLength // 4
    
    v1.byteOffset // 0
    v2.byteOffset // 2
    v3.byteOffset // 2

    TypedArray.prototype.length

    length属性表示TypedArray数组含有多少个成员。注意将byteLength属性和length属性区分,前者是字节长度,后者是成员长度。

    var a = new Int16Array(8);
    
    a.length // 8
    a.byteLength // 16
    TypedArray.prototype.set()

    TypedArray数组的set方法用于复制数组(正常数组或TypedArray数组),也就是将一段内容完全复制到另一段内存。

    var a = new Uint8Array(8);
    var b = new Uint8Array(8);
    
    b.set(a);

    上面代码复制a数组的内容到b数组,它是整段内存的复制,比一个个拷贝成员的那种复制快得多。set方法还可以接受第二个参数,表示从b对象哪一个成员开始复制a对象。

    var a = new Uint16Array(8);
    var b = new Uint16Array(10);
    
    b.set(a, 2)

    上面代码的b数组比a数组多两个成员,所以从b[2]开始复制。

    TypedArray.prototype.subarray()

    subarray方法是对于TypedArray数组的一部分,再建立一个新的视图。

    var a = new Uint16Array(8);
    var b = a.subarray(2,3);
    
    a.byteLength // 16
    b.byteLength // 2

    subarray方法的第一个参数是起始的成员序号,第二个参数是结束的成员序号(不含该成员),如果省略则包含剩余的全部成员。所以,上面代码的a.subarray(2,3),意味着b只包含a[2]一个成员,字节长度为2。

    TypedArray.prototype.slice()
    TypeArray实例的slice方法,可以返回一个指定位置的新的TypedArray实例。
    
    let ui8 = Uint8Array.of(0, 1, 2);
    ui8.slice(-1)
    // Uint8Array [ 2 ]

    上面代码中,ui8是8位无符号整数数组视图的一个实例。它的slice方法可以从当前视图之中,返回一个新的视图实例。

    slice方法的参数,表示原数组的具体位置,开始生成新数组。负值表示逆向的位置,即-1为倒数第一个位置,-2表示倒数第二个位置,以此类推。

    TypedArray.of()

    TypedArray数组的所有构造函数,都有一个静态方法of,用于将参数转为一个TypedArray实例。

    Float32Array.of(0.151, -8, 3.7)
    // Float32Array [ 0.151, -8, 3.7 ]

    TypedArray.from()

    静态方法from接受一个可遍历的数据结构(比如数组)作为参数,返回一个基于这个结构的TypedArray实例。

    Uint16Array.from([0, 1, 2])
    // Uint16Array [ 0, 1, 2 ]

    这个方法还可以将一种TypedArray实例,转为另一种。

    var ui16 = Uint16Array.from(Uint8Array.of(0, 1, 2));
    ui16 instanceof Uint16Array // true

    from方法还可以接受一个函数,作为第二个参数,用来对每个元素进行遍历,功能类似map方法。

    Int8Array.of(127, 126, 125).map(x => 2 * x)
    // Int8Array [ -2, -4, -6 ]
    
    Int16Array.from(Int8Array.of(127, 126, 125), x => 2 * x)
    // Int16Array [ 254, 252, 250 ]

    上面的例子中,from方法没有发生溢出,这说明遍历是针对新生成的16位整数数组,而不是针对原来的8位整数数组。也就是说,from会将第一个参数指定的TypedArray数组,拷贝到另一段内存之中(占用内存从3字节变为6字节),然后再进行处理。

    复合视图

    由于视图的构造函数可以指定起始位置和长度,所以在同一段内存之中,可以依次存放不同类型的数据,这叫做“复合视图”。

    var buffer = new ArrayBuffer(24);
    
    var idView = new Uint32Array(buffer, 0, 1);
    var usernameView = new Uint8Array(buffer, 4, 16);
    var amountDueView = new Float32Array(buffer, 20, 1);

    上面代码将一个24字节长度的ArrayBuffer对象,分成三个部分:

    字节0到字节3:1个32位无符号整数
    字节4到字节19:16个8位整数
    字节20到字节23:1个32位浮点数
    这种数据结构可以用如下的C语言描述:

    struct someStruct {
      unsigned long id;
      char username[16];
      float amountDue;
    };

    DataView视图

    如果一段数据包括多种类型(比如服务器传来的HTTP数据),这时除了建立ArrayBuffer对象的复合视图以外,还可以通过DataView视图进行操作。

    DataView视图提供更多操作选项,而且支持设定字节序。本来,在设计目的上,ArrayBuffer对象的各种TypedArray视图,是用来向网卡、声卡之类的本机设备传送数据,所以使用本机的字节序就可以了;而DataView视图的设计目的,是用来处理网络设备传来的数据,所以大端字节序或小端字节序是可以自行设定的。

    DataView视图本身也是构造函数,接受一个ArrayBuffer对象作为参数,生成视图。

    DataView(ArrayBuffer buffer [, 字节起始位置 [, 长度]]);
    下面是一个例子。

    var buffer = new ArrayBuffer(24);
    var dv = new DataView(buffer);

    DataView实例有以下属性,含义与TypedArray实例的同名方法相同。

    DataView.prototype.buffer:返回对应的ArrayBuffer对象
    DataView.prototype.byteLength:返回占据的内存字节长度
    DataView.prototype.byteOffset:返回当前视图从对应的ArrayBuffer对象的哪个字节开始
    DataView实例提供8个方法读取内存。

    getInt8:读取1个字节,返回一个8位整数。
    getUint8:读取1个字节,返回一个无符号的8位整数。
    getInt16:读取2个字节,返回一个16位整数。
    getUint16:读取2个字节,返回一个无符号的16位整数。
    getInt32:读取4个字节,返回一个32位整数。
    getUint32:读取4个字节,返回一个无符号的32位整数。
    getFloat32:读取4个字节,返回一个32位浮点数。
    getFloat64:读取8个字节,返回一个64位浮点数。
    这一系列get方法的参数都是一个字节序号(不能是负数,否则会报错),表示从哪个字节开始读取。

    var buffer = new ArrayBuffer(24);
    var dv = new DataView(buffer);
    
    // 从第1个字节读取一个8位无符号整数
    var v1 = dv.getUint8(0);
    
    // 从第2个字节读取一个16位无符号整数
    var v2 = dv.getUint16(1);
    
    // 从第4个字节读取一个16位无符号整数
    var v3 = dv.getUint16(3);

    上面代码读取了ArrayBuffer对象的前5个字节,其中有一个8位整数和两个十六位整数。

    如果一次读取两个或两个以上字节,就必须明确数据的存储方式,到底是小端字节序还是大端字节序。默认情况下,DataView的get方法使用大端字节序解读数据,如果需要使用小端字节序解读,必须在get方法的第二个参数指定true。

    // 小端字节序
    var v1 = dv.getUint16(1, true);
    
    // 大端字节序
    var v2 = dv.getUint16(3, false);
    
    // 大端字节序
    var v3 = dv.getUint16(3);

    DataView视图提供8个方法写入内存。

    setInt8:写入1个字节的8位整数。
    setUint8:写入1个字节的8位无符号整数。
    setInt16:写入2个字节的16位整数。
    setUint16:写入2个字节的16位无符号整数。
    setInt32:写入4个字节的32位整数。
    setUint32:写入4个字节的32位无符号整数。
    setFloat32:写入4个字节的32位浮点数。
    setFloat64:写入8个字节的64位浮点数。
    这一系列set方法,接受两个参数,第一个参数是字节序号,表示从哪个字节开始写入,第二个参数为写入的数据。对于那些写入两个或两个以上字节的方法,需要指定第三个参数,false或者undefined表示使用大端字节序写入,true表示使用小端字节序写入。

    // 在第1个字节,以大端字节序写入值为25的32位整数
    dv.setInt32(0, 25, false);
    
    // 在第5个字节,以大端字节序写入值为25的32位整数
    dv.setInt32(4, 25);
    
    // 在第9个字节,以小端字节序写入值为2.5的32位浮点数
    dv.setFloat32(8, 2.5, true);
    如果不确定正在使用的计算机的字节序,可以采用下面的判断方式。
    
    var littleEndian = (function() {
      var buffer = new ArrayBuffer(2);
      new DataView(buffer).setInt16(0, 256, true);
      return new Int16Array(buffer)[0] === 256;
    })();

    如果返回true,就是小端字节序;如果返回false,就是大端字节序。

    二进制数组的应用

    大量的Web API用到了ArrayBuffer对象和它的视图对象。

    AJAX

    传统上,服务器通过AJAX操作只能返回文本数据,即responseType属性默认为text。XMLHttpRequest第二版XHR2允许服务器返回二进制数据,这时分成两种情况。如果明确知道返回的二进制数据类型,可以把返回类型(responseType)设为arraybuffer;如果不知道,就设为blob。

    var xhr = new XMLHttpRequest();
    xhr.open('GET', someUrl);
    xhr.responseType = 'arraybuffer';
    
    xhr.onload = function () {
      var let arrayBuffer = xhr.response;
      // ···
    };
    
    xhr.send();

    如果知道传回来的是32位整数,可以像下面这样处理。

    xhr.onreadystatechange = function () {
      if (req.readyState === 4 ) {
        var arrayResponse = xhr.response;
        var dataView = new DataView(arrayResponse);
        var ints = new Uint32Array(dataView.byteLength / 4);
    
        xhrDiv.style.backgroundColor = "#00FF00";
        xhrDiv.innerText = "Array is " + ints.length + "uints long";
      }
    }

    Canvas

    网页Canvas元素输出的二进制像素数据,就是类型化数组。

    var canvas = document.getElementById('myCanvas');
    var ctx = canvas.getContext('2d');
    
    var imageData = ctx.getImageData(0, 0, canvas.width, canvas.height);
    var uint8ClampedArray = imageData.data;

    需要注意的是,上面代码的typedArray虽然是一个类型化数组,但是它的视图类型是一种针对Canvas元素的专有类型Uint8ClampedArray。这个视图类型的特点,就是专门针对颜色,把每个字节解读为无符号的8位整数,即只能取值0~255,而且发生运算的时候自动过滤高位溢出。这为图像处理带来了巨大的方便。

    举例来说,如果把像素的颜色值设为Uint8Array类型,那么乘以一个gamma值的时候,就必须这样计算:

    u8[i] = Math.min(255, Math.max(0, u8[i] * gamma));

    因为Uint8Array类型对于大于255的运算结果(比如0xFF+1),会自动变为0x00,所以图像处理必须要像上面这样算。这样做很麻烦,而且影响性能。如果将颜色值设为Uint8ClampedArray类型,计算就简化许多。

    pixels[i] *= gamma;

    Uint8ClampedArray类型确保将小于0的值设为0,将大于255的值设为255。注意,IE 10不支持该类型。

    WebSocket

    WebSocket可以通过ArrayBuffer,发送或接收二进制数据。

    var socket = new WebSocket('ws://127.0.0.1:8081');
    socket.binaryType = 'arraybuffer';
    
    // Wait until socket is open
    socket.addEventListener('open', function (event) {
      // Send binary data
      var typedArray = new Uint8Array(4);
      socket.send(typedArray.buffer);
    });
    
    // Receive binary data
    socket.addEventListener('message', function (event) {
      var arrayBuffer = event.data;
      // ···
    });

    Fetch API

    Fetch API取回的数据,就是ArrayBuffer对象。

    fetch(url)
    .then(function(request){
      return request.arrayBuffer()
    })
    .then(function(arrayBuffer){
      // ...
    });

    File API

    如果知道一个文件的二进制数据类型,也可以将这个文件读取为ArrayBuffer对象。

    var fileInput = document.getElementById('fileInput');
    var file = fileInput.files[0];
    var reader = new FileReader();
    reader.readAsArrayBuffer(file);
    reader.onload = function () {
      var arrayBuffer = reader.result;
      // ···
    };

    下面以处理bmp文件为例。假定file变量是一个指向bmp文件的文件对象,首先读取文件。

    var reader = new FileReader();
    reader.addEventListener("load", processimage, false);
    reader.readAsArrayBuffer(file);

    然后,定义处理图像的回调函数:先在二进制数据之上建立一个DataView视图,再建立一个bitmap对象,用于存放处理后的数据,最后将图像展示在canvas元素之中。

    function processimage(e) {
      var buffer = e.target.result;
      var datav = new DataView(buffer);
      var bitmap = {};
      // 具体的处理步骤
    }

    具体处理图像数据时,先处理bmp的文件头。具体每个文件头的格式和定义,请参阅有关资料。

    bitmap.fileheader = {};
    bitmap.fileheader.bfType = datav.getUint16(0, true);
    bitmap.fileheader.bfSize = datav.getUint32(2, true);
    bitmap.fileheader.bfReserved1 = datav.getUint16(6, true);
    bitmap.fileheader.bfReserved2 = datav.getUint16(8, true);
    bitmap.fileheader.bfOffBits = datav.getUint32(10, true);

    接着处理图像元信息部分。

    bitmap.infoheader = {};
    bitmap.infoheader.biSize = datav.getUint32(14, true);
    bitmap.infoheader.biWidth = datav.getUint32(18, true);
    bitmap.infoheader.biHeight = datav.getUint32(22, true);
    bitmap.infoheader.biPlanes = datav.getUint16(26, true);
    bitmap.infoheader.biBitCount = datav.getUint16(28, true);
    bitmap.infoheader.biCompression = datav.getUint32(30, true);
    bitmap.infoheader.biSizeImage = datav.getUint32(34, true);
    bitmap.infoheader.biXPelsPerMeter = datav.getUint32(38, true);
    bitmap.infoheader.biYPelsPerMeter = datav.getUint32(42, true);
    bitmap.infoheader.biClrUsed = datav.getUint32(46, true);
    bitmap.infoheader.biClrImportant = datav.getUint32(50, true);

    最后处理图像本身的像素信息。

    var start = bitmap.fileheader.bfOffBits;
    bitmap.pixels = new Uint8Array(buffer, start);

    至此,图像文件的数据全部处理完成。下一步,可以根据需要,进行图像变形,或者转换格式,或者展示在Canvas网页元素之中。

    展开全文
  • java eclipse源码jadclipse JadClipse是一个Eclipse插件,可以反编译Java二进制文件以允许查看其源代码
  • piperun是一个简单的C程序,它允许您执行从标准输入读取的已编译ELF二进制文件。 用法 gcc -c t/hello.c -o /dev/stdout | ./piperun 或者 make check 只需运行make然后将已编译的ELF二进制文件通过./pipeprun到....
  • 一个研究项目,研究ARM64到ARM64二进制转换,该转换允许在运行时根据用户规范对机器代码进行检测。 什么是二进制翻译 二进制翻译是一种在虚拟机和仿真器中常见的技术,在该技术中,程序需要获取并修改其机器代码。 ...
  • 动态二进制树搜索算法 二进制搜索树 (Binary Search Tree) A binary search tree is a useful data structure for fast addition and removal of data. 二进制搜索树是用于快速添加和删除数据的有用数据结构。 It...

    动态二进制树搜索算法

    A binary search tree is a useful data structure for fast addition and removal of data.

    二进制搜索树是用于快速添加和删除数据的有用数据结构。

    It is composed of nodes, which stores data and also links to upto two other child nodes. It is the relationship between the leaves linked to and the linking leaf, also known as the parent node, which makes the binary tree such an efficient data structure.

    它由节点组成,节点存储数据并链接到最多两个其他子节点。 链接到的叶子与链接叶子(也称为父节点)之间的关系使二叉树成为一种高效的数据结构。

    For a binary tree to be a binary search tree, the data of all the nodes in the left sub-tree of the root node should be less than the data of the root. The data of all the nodes in the right subtree of the root node should be greater than equal to the data of the root. As a result, the leaves on the farthest left of the tree have the lowest values, whereas the leaves on the right of the tree have the greatest values.

    为了使二叉树成为二叉搜索树,根节点左子树中所有节点的数据应小于根节点的数据。 根节点右子树中所有节点的数据应大于等于根节点的数据。 结果,树最左边的叶子具有最低的值,而树右边的叶子具有最大的值。

    A representation of binary search tree looks like the following:

    二进制搜索树的表示形式如下所示:

    Binary Search Tree

    Consider the root node 20. All elements to the left of subtree(10, 5) are less than 20 and all elements to the right of subtree(25, 30, 35) are greater than 20.

    考虑根节点20。子树(10,5)左侧的所有元素都小于20,子树(25,30,35)右侧的所有元素都大于20。

    实施BST (Implementation of BST)

    First, define a struct as tree_node. It will store the data and pointers to left and right subtree.

    首先,将一个结构定义为tree_node 。 它将存储数据以及指向左和右子树的指针。

    struct tree_node
    {
    	int data;
    	tree_node *left, *right;
    };

    The node itself is very similar to the node in a linked list. A basic knowledge of the code for a linked list will be very helpful in understanding the techniques of binary trees.

    该节点本身与链表中的节点非常相似。 链表代码的基本知识将有助于理解二叉树的技术。

    It is most logical to create a binary search tree class to encapsulate the workings of the tree into a single area, and also making it reusable. The class will contain functions to insert data into the tree, search if the data is present and methods for traversing the tree.

    创建二进制搜索树类以将树的工作封装到单个区域中并使其可重用是最合乎逻辑的。 该类将包含将数据插入树中,搜索数据是否存在以及遍历树的方法的函数。

    class BST
    {
    	tree_node *root;
    	void insert(tree_node* , int );
    	bool search(int , tree_node* );
    	void inorder(tree_node* );
    	void preorder(tree_node* );
    	void postorder(tree_node* );
    
    	public:
    	BST()
    	{
    		root = NULL;
    	}
    	void insert(int );
    	bool search(int key);
        void inorder();
        void preorder();
        void postorder();
    };

    It is necessary to initialize root to NULL for the later functions to be able to recognize that it does not exist.

    必须将root初始化为NULL,以便以后的功能能够识别它不存在。

    All the public members of the class are designed to allow the user of the class to use the class without dealing with the underlying design. The functions which will be called recursively are the ones which are private, allowing them to travel down the tree.

    该类的所有公共成员都被设计为允许该类的用户使用该类,而无需处理基础设计。 将被递归调用的函数是私有的,从而使它们可以向下移动。

    插入BST (Insertion in a BST)

    To insert data into a binary tree involves a function searching for an unused node in the proper position in the tree in which to insert the key value. The insert function is generally a recursive function that continues moving down the levels of a binary tree until there is an unused leaf in a position which follows the following rules of placing nodes.

    将数据插入二叉树涉及到一个函数,该函数在树中要插入键值的适当位置中搜索未使用的节点。 插入函数通常是递归函数,它继续向下移动二叉树的级别,直到某个位置上有未使用的叶子为止,该叶子遵循以下放置节点的规则。

    • Compare data of the root node and element to be inserted.

      比较根节点和要插入的元素的数据。

    • If the data of the root node is greater, and if a left subtree exists, then repeat step 1 with root = root of left subtree. Else,

      如果根节点的数据更大,并且存在左子树,则使用root = left subtree的root重复步骤1。 其他,

    • Insert element as left child of current root.

      插入元素作为当前根的左子元素。

    • If the data of the root node is greater, and if a right subtree exists, then repeat step 1 with root = root of right subtree.

      如果根节点的数据更大,并且存在右子树,则使用root = right subtree的root重复步骤1。

    • Else, insert element as right child of current root.

      否则,将元素插入为当前根的右子元素。

    Binary Search Tree
    void BST :: insert(tree_node *node, int d)
    {
    	// element to be inserted is lesser than node’s data
    	if(d < node->data)
    	{
    		// if left subtree is present
    		if(node->left != NULL)
    			insert(node->left, d);
    		
    		// create new node
    		else
    		{
    			node->left = new tree_node;
    			node->left->data = d;
    			node->left->left = NULL;
    			node->left->right = NULL;
    		}
    	}
    
    	// element to be inserted is greater than node’s data
    	else if(d >= node->data)
    	{
    		// if left subtree is present
    		if(node->right != NULL)
    			insert(node->right, d);
    		
    		// create new node
    		else
    		{
    			node->right = new tree_node;
    			node->right->data = d;
    			node->right->left = NULL;
    			node->right->right = NULL;
    		}
    	}
    	
    }

    Since the root node is a private member, we also write a public member function which is available to non-members of the class. It calls the private recursive function to insert an element and also takes care of the case when root node is NULL.

    由于根节点是私有成员,因此我们还编写了一个公共成员函数,该函数可供该类的非成员使用。 它调用私有递归函数来插入元素,并且还要注意当根节点为NULL时的情况。

    void BST::insert(int d)
    {
    	if(root!=NULL)
                    insert(root, d);
    	else
        {
            root = new tree_node;
            root->data = d;
            root->left = NULL;
            root->right = NULL;
        }
    }

    在BST中搜索 (Searching in a BST)

    The search function works in a similar fashion as insert. It will check if the key value of the current node is the value to be searched. If not, it should check to see if the value to be searched for is less than the value of the node, in which case it should be recursively called on the left child node, or if it is greater than the value of the node, it should be recursively called on the right child node.

    搜索功能的工作方式与插入类似。 它将检查当前节点的键值是否为要搜索的值。 如果不是,则应检查要搜索的值是否小于节点的值,在这种情况下,应在左侧的子节点上递归调用该值,或者应大于节点的值,应该在正确的子节点上递归调用它。

    • Compare data of the root node and the value to be searched.

      比较根节点的数据和要搜索的值。

    • If the data of the root node is greater, and if a left subtree exists, then repeat step 1 with root = root of left subtree. Else,

      如果根节点的数据更大,并且存在左子树,则使用root = left subtree的root重复步骤1。 其他,

    • If the data of the root node is greater, and if a right subtree exists, then repeat step 1 with root = root of right subtree. Else,

      如果根节点的数据更大,并且存在右子树,则使用root = right subtree的root重复步骤1。 其他,

    • If the value to be searched is equal to the data of root node, return true.

      如果要搜索的值等于根节点的数据,则返回true。

    • Else, return false.

      否则,返回false。

    bool BST::search(int d, tree_node *node)
    {
    	bool ans = false;
    
    	// node is not present
      	if(node == NULL)
     		return false;
    	
    	// Node’s data is equal to value searched
        if(d == node->data)
          	return true;
    	
    	// Node’s data is greater than value searched
        else if(d < node->data)
           	ans = search(d, node->left);
    
    	// Node’s data is lesser than value searched
        else
           	ans = search(d, node->right);
      
        return ans;
    }

    Since the root node is a private member, we also write a public member function which is available to non-members of the class. It calls the private recursive function to search an element and also takes care of the case when root node is NULL.

    由于根节点是私有成员,因此我们还编写了一个公共成员函数,该函数可供该类的非成员使用。 它调用私有递归函数来搜索元素,并且还要注意根节点为NULL的情况。

    bool BST::search(int d)
    {
    	if(root ==  NULL)
    		return false;
    	else	
    		return  search(d, root);
    }

    在BST中遍历 (Traversing in a BST)

    There are mainly three types of tree traversals:

    树遍历主要有三种类型:

    1.预定遍历: (1. Pre-order Traversal:)

    In this technique, we do the following :

    在此技术中,我们执行以下操作:

    • Process data of root node.

      根节点的处理数据。

    • First, traverse left subtree completely.

      首先,完全遍历左子树。

    • Then, traverse right subtree.

      然后,遍历右子树。

    void BST :: preorder(tree_node *node)
    {
    	if(node !=  NULL)
        {
    		cout<<node->data<<endl;
           	preorder(node->left);
           	preorder(node->right);
        }
    }

    2.订单遍历 (2. Post-order Traversal)

    In this traversal technique we do the following:

    在这种遍历技术中,我们执行以下操作:

    • First traverse left subtree completely.

      完全遍历左子树。

    • Then, traverse right subtree completely.

      然后,完全遍历右子树。

    • Then, process data of node.

      然后,处理节点的数据。

    void BST :: postorder(tree_node *node)
    {
    	if(node !=  NULL)
       	{
            postorder(node->left);
            postorder(node->right);
    	    cout<<node->data<<endl;
       	}
    }

    3.有序遍历 (3. In-order Traversal)

    In in-order traversal, we do the following:

    在有序遍历中,我们执行以下操作:

    • First process left subtree.

      首先处理左子树。

    • Then, process current root node.

      然后,处理当前的根节点。

    • Then, process right subtree.

      然后,处理右子树。

    void BST :: inorder(tree_node *node)
    {
    	if(node !=  NULL)
       	{
            inorder(node->left);
    	    cout<<node->data<<endl;
            inorder(node->right);
       	}
    }

    The in-order traversal of a binary search tree gives a sorted ordering of the data elements that are present in the binary search tree. This is an important property of a binary search tree.

    二进制搜索树的有序遍历给出了二进制搜索树中存在的数据元素的排序顺序。 这是二进制搜索树的重要属性。

    Since the root node is a private member, we also write public member functions which is available to non-members of the class. It calls the private recursive function to traverse the tree and also takes care of the case when root node is NULL.

    由于根节点是私有成员,因此我们还编写了公共成员函数,该函数可供该类的非成员使用。 它调用私有递归函数遍历树,并且还照顾根节点为NULL的情况。

    void BST :: preorder()
    {
    	if(root ==  NULL)
    		cout<<"TREE IS  EMPTY\n";
    	else
           	preorder(root);
    }
    
    void BST :: postorder()
    {
    	if(root ==  NULL)
    		cout<<"TREE IS  EMPTY\n";
    	else
    	    postorder(root);
    }
    
    void BST :: inorder()
    {
    	if(root == NULL)
    		cout<<"TREE IS EMPTY\n";
    	else
    		inorder(root);
    }

    复杂度分析 (Complexity Analysis)

    Binary Search Tree

    The time complexity of search and insert rely on the height of the tree. On average, binary search trees with n nodes have O(log n) height. However in the worst case the tree can have a height of O(n) when the unbalanced tree resembles a linked list. For example in this case :

    搜索和插入的时间复杂度取决于树的高度。 平均而言,具有n个节点的二叉搜索树的高度为O(log n) 。 但是,在最坏的情况下,当不平衡树类似于链表时,树的高度可能为O(n) 。 例如在这种情况下:

    Binary Search Tree

    Traversal requires O(n) time, since every node must be visited.

    遍历需要O(n)时间,因为必须访问每个节点。

    翻译自: https://www.studytonight.com/data-structures/binary-search-tree

    动态二进制树搜索算法

    展开全文
  • 二进制、八进制、十进制、十六进制关系及转换

    万次阅读 多人点赞 2019-02-21 21:20:22
    二进制,八进制,十进制,十六进制之间的关系是什么?浮点数是什么回事? 本文内容参考自王达老师的《深入理解计算机网络》一书&amp;amp;amp;amp;amp;amp;amp;amp;amp;lt;中国水利水电出版社&amp;amp;amp;amp...
  • 计算机中的数据可分为两种类型:数字和字符,它们最终都要转换为二进制代码进行存储和处理。对于人们习惯的十进制数字,通常用____进行转换。更多相关问题[单选] 电力线路巡视检查周期,定期巡视每月至少()。[单选] ...
  • ASCII码划分为两个集合:128个字符的标准ASCII码(7位二进制编码)和附加的128个字符的扩展ASCII码(8位二进制编码)。...ASCII码:美国(国家)信息交换标准(代)码,一种使用7个或8个二进制位进行编码的方案,最多可以给...
  • Linux 二进制分析

    千次阅读 2018-11-06 11:55:21
    二进制分析属于信息安全业界逆向工程中的一种技术,通过利用可执行的机器代码二进制)来分析应用程序的控制结构和运行方式,有助于信息安全从业人员更好地分析各种漏洞、病毒以及恶意软件,从而找到相应的解决方案...
  • 十六进制和二进制转储 布莱恩·阿兰提科(Brian ... 第二个命令允许您转储文件中数据的二进制表示形式。 新颖/重要的设计决策的列表/说明:3个源代码文件和一个头文件用于构建程序。 Main.cpp包含main方法,fio.cpp
  • C语言读写二进制文件

    万次阅读 2017-07-20 14:35:04
    可以这么说,除了文本文件以外的所有文件都是二进制文件。二进制文件相对于文本文件更容易修改。因为文本文件的修改,需要修改以后写入内存,然后再清空原文件,再从内存中读取出修改以后的内容到本文件中。二进制...
  • 初识二进制文件

    2020-03-25 19:01:17
    计算机文件 一般分为两类:二进制文件 和 ASCII文件(也称纯文本文件)。 ASCII文件:用纯文本编辑器能够打开且打开文件的内容是人类能够理解的可显示字符。 二进制文件:狭义的说,除去纯文本文件以外的文件均为...
  • JS十进制转二进制

    千次阅读 2020-08-01 08:52:00
    如果bin-bit小于转化后的二进制本身位数,则使用原本的位数,如dec-number为5,bin-bit为2,依然输出101,但同时在console中报个错。 一、十进制转二进制,不控制位数。 <!DOCTYPE html> <html> <...
  • 二进制-文本互转工具

    千次下载 热门讨论 2010-11-26 15:03:00
    使用方法:二进制转文本的时候只能通过文件方式转换,即二进制数据必须是文件形式(因为我们手写不能直观的表示二进制),转换后的文本同时保存为文件和文本框显示2种方式。 文本转二进制的时候可以通过文件和输入...
  • MySql 二进制类型

    千次阅读 2015-10-25 15:04:58
    MySQL二进制类型 二进制类型是在数据库中存储二进制数据的数据类型。二进制类型包括BINARY、VARBINARY、BIT、TINYBLOB、BLOB、MEDIUMBLOB和...字节数为M字节,允许长度为0~M的固定长度二进制字符串 VARB
  • 作为一名图书馆作家,如何不断验证我不会破坏二进制兼容性? semantic-versioning是一个Java库,它允许验证(使用字节码检查)库版本号是否遵循由定义的控制原则。 它可以检查JAR文件或类,以识别版本之间的更改,...
  • 扩展二进制

    2017-09-22 09:47:50
    有一天小Hi突发奇想:如果允许使用数字2会发生什么事情?小Hi称其为扩展二进制数,例如(21)ii = 2 * 21 + 1 = 5, (112)ii = 1 * 22 + 1 * 21 + 2 = 8。 很快小Hi意识到在扩展二进制中,每个数的表示方法不是...
  • 原有页面是展示一堆图片,这些图片从后台获取的,后台直接往outputStream输出图片的二进制数据,前端通过img标签的src属性来显示这些图片 现在由于增加了鉴权功能,使用的jwt,往http header里面放jwt来鉴权的,然后...
  • BinNavi是一个二进制分析IDE,该环境使用户可以检查,导航,编辑和注释反汇编代码的控制流图,对可执行文件的调用图执行相同的操作,收集和合并执行跟踪,并通常进行跟踪一组分析师之间的分析结果。 注意:BinNavi...
  • java编程基础(一)二进制

    千次阅读 2020-07-11 23:03:49
    文章目录二进制bit 和 bytejava 中的 byte 类型java 中 byte 类型表示正数:java 中 byte 类型表示负数:四种整数类型的最小和最大值二进制和十进制的互转练一练java 代码中直接写二进制字面值 二进制 对于任何已知...
  • 二进制文件和 ASCII

    千次阅读 2019-03-20 09:59:44
    计算机文件基本上分为二种:二进制文件和 ASCII(也称纯文本文件) 文本文件是可以看到的字符,二进制文件是不可视字符,如图片. 二进制文件: 包含在ASCII及扩展 ASCII字符中编写的数据或程序指令的文件。计算机文件...
  • 允许将Mailman集成到动态网站中,而无需使用Python或需要对Mailman二进制文件的许可。 @类别服务 @package邮递员 @作者詹姆斯·韦德 @版权所有2011 James Wade @license BSD许可证 @version版本:@ package_...
  • 二进制数组的操作

    千次阅读 2018-09-14 04:25:10
    ES6之前是不能通过代码直接操作二进制数据的,为了方便开发者可以直接操作二进制数据,ES6提出了三个操作二进制数据的接口:ArrayBuffer、TypedArray和DataView ArrayBuffer ArrayBuffer代表储存二进制数据的一段...
  • 今天,项目现场提出这样一种需求:项目中,将项目文件打成zip包进行发布时,由于安全机制的限制,不允许发布二进制文件,因此需要将.zip格式的二进制文件encode成文本文件,再将文本文件上传后decode成.zip格式。...
  • 全国许多用人单位都已把全国高等学校计算机等级考试证书作为衡量计算机 应用水平高低的标准。... 集成电路答案:A3、机器指令是由二进制代码表示的,它能被计算机( )执行。a. 编译后 b. 直接 c. 解释后 d. ...
  • 使用二进制数枚举子集

    千次阅读 2015-01-06 11:56:42
    问题描述:枚举给定集合的所有子集,包括只含一...思路:利用二进制的“开关”特性枚举,具体为:假设给定集合A大小为n,则想象A = {a[0], a[1], ..., a[n-1]}的每个元素对应一个开关位(0或1),0表示不出现,1表示出
  • 二进制、八进制、十六进制 6.1 为什么需要八进制和十六进制? 6.2 二、八、十六进制数转换到十进制数  6.2.1 二进制数转换为十进制数  6.2.2 八进制数转换为十进制数  6.2.3 八进制数的表达方法 ...
  • 读写二进制文件

    2013-04-14 19:55:47
    fopen , fread fwrite 函数读写...在使用 fread 读二进制文件(png 图片)的时候, 发现读取到内存中的数据和 二进制文件中的数据不一致, 同样, 在 使用 fwrite 写二进制文件(png 图片)的时候, 发现写入到内存

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 315,777
精华内容 126,310
关键字:

二进制允许使用的代码