Как «повернуть» двоичные данные (по горизонтали), если их размер больше 32 бит?

У меня есть следующий TypedArray (обратите внимание, что размер этих данных составляет 80 бит):

var arr = new Uint8Array([10, 110, 206, 117, 200, 35, 99, 2, 98, 125]);

и я хочу повернуть его на N бит (где N — любое целое число от 0 до 79). Например, если N=50, я представлю это так:

00001010 01101110 11001110 01110101 11001000 00100011 01100011 00000010 01100010 01111101
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

так что результат должен быть

01101100 01100000 01001100 01001111 10100001 01001101 11011001 11001110 10111001 00000100
                                       ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

поэтому arr[0] будет равно 108, arr[1] будет равно 96 и т. д. Как это решить?


javascript typed-arrays bit-manipulation bitwise-operators
person lyrically wicked    schedule 16.03.2017    source источник

Ответы (1)


arrow_upward
3
arrow_downward

Чтобы сдвинуть весь массив байтов побитно, вы можете сделать:

  • Сначала подсчитайте, сколько байтов можно сдвинуть (var bytes = (bits / 8)|0;)
  • Скопируйте количество байтов с одного конца, сдвиньте байты, вставьте предыдущий фрагмент на противоположном конце
  • Проверить, остались ли какие-либо биты (var rester = bits % 8)
  • Если остался какой-либо остаток (!=0), выполните цикл, скопируйте и сдвиньте предыдущий байт на количество битов в противоположном направлении и 8 оставшихся битов (var prev = arr[arr.length - 1] << (8- remainder);) (подробности см. в демо).
  • Сдвинуть байт и объединить с предыдущим сдвинутым байтом (arr[i] = (arr[i]>>>remainder) | prev;)

Демо

// main rotation function
function rotate(arr, bits) {

  var arrBits = arr.length<<3;
  var aBits = Math.abs(bits) % arrBits;       // "clamp" and make positive value
  aBits = bits < 0 ? arrBits - aBits : aBits; // direction

  var bytes = (aBits / 8)|0;       // how many bytes we can pre-rotate
  var remainder = aBits % 8;       // number of additional bits that needs to rotate
  var iRemainder = 8 - remainder;  // inverse (cached for convenience)
  var first;                       // first shift added to end

  // first rotate based on number of whole bytes, get slice of end
  var rBytes = arr.slice(arr.length - bytes);
   
  // shift over remainding array byte-wise
  arr.copyWithin(bytes, 0);
   
  // set previous slice from end to beginning
  arr.set(rBytes);
   
  // shift remainders, if any (>0)
  if (remainder) {
    first = (arr[arr.length - 1] << iRemainder);    // need this at the end
	
    for(var i = arr.length-1; i > 0; i--) {         // iterate in reverse
      var prev = (arr[i - 1] << iRemainder);        // get previous byte shifted
      arr[i] = (arr[i]>>>remainder) | prev;         // shift current, merge w/prev
    }
    arr[0] = (arr[0]>>>remainder) | first           // shift last and merge w/first
  }
}

// DEMO STUFF -
var rng = document.getElementById("bits");
var cnt = document.getElementById("cnt");
var out = document.getElementById("out");
function toBin(arr) {
  for(var i=0, str="", str2=""; i < arr.length; i++) {
    str+= pad(arr[i]) + " ";
    str2 += arr[i].toString() + " ";
  }
  return str.replace(/0/g, "<span class=c>0</span>") + "<br>" + str2;
}
function pad(b) {
  var s = "00000000" + b.toString(2);
  return s.substr(s.length - 8)
}
function update() {
  var arr = new Uint8Array([10, 110, 206, 117, 200, 35, 99, 2, 98, 125]);
  cnt.innerHTML = rng.value;  rotate(arr, +rng.value); out.innerHTML = toBin(arr)
}
update(); rng.oninput = update;
body {font:16px sans-serif;margin-left:0}
#out {font:12px monospace;white-space:nowrap}
.c {color:#999} div {margin-top:10px}
<label>Bits: <input id=bits type=range min=-80 max=80 value=0></label> <span id=cnt>0</span>
<div id=out></div>

Чтобы повернуть в противоположном направлении, просто вычтите количество битов из общего количества битов (arrayByteLength x 8 - биты), просто не забудьте применить результат по модулю на основе длины массива.

person Community    schedule 16.03.2017
comment
Спасибо. Два вопроса: 1) в If, скопировать и сдвинуть предыдущий байт... — означает ли это, что что-то пропущено между if и запятой? Если (условие), то скопировать и сдвинуть...? 2) не забудьте отменить знак, т.е. v›››0-›unsigned — где именно отменить знак, что такое "v"? - person lyrically wicked; 16.03.2017
comment
@lyrallywicked Если скопировать и сдвинуть предыдущий байт, если какой-либо остаток требуется в дополнение к байтовому сдвигу. Отмените знак, потому что, если он подписан, число будет дополнено 1, если оно отрицательное (т. е. -1››8 не совпадает с -1›››8). v предназначалось для обозначения значения, например, любого значения, с которым сталкивается цикл. Дайте мне знать, если вам нужна дополнительная информация. (ответ обновлен) - person ; 16.03.2017