Как добавить биты в JavaScript - PullRequest
Новая
       27

Как добавить биты в JavaScript

0 голосов
/ 25 августа 2018

Скажем, у вас есть два целых числа 10 и 20. Это 00001010 и 00010100. Затем я хотел бы просто объединить их как строки, но в результате получить новое целое число. 

00001010 + 00010100 == 0000101000010100

Это окончательное число 2580.

Однако я ищу способ сделать это без фактического преобразования их в строку. Ищите что-то более эффективное, что просто немного изменяет целые числа. Я не слишком знаком с этим, но я думаю, что это будет примерно так: 

var a = 00001010 // == 10
var b = 00010100 // == 20
var c = a << b //   == 2580

Обратите внимание, я бы хотел, чтобы это работало с любыми последовательностями битов. Итак, даже: 

var a = 010101
var b = 01110
var c = a + b == 01010101110

Ответы [ 3 ]

0 голосов
/ 26 августа 2018

Обратите внимание, я бы хотел, чтобы это работало с любыми последовательностями битов. Итак, даже: 

var a = 010101
var b = 01110
var c = a + b == 01010101110

Это не будет возможно, если вы не преобразуете в строку или не сохраняете количество бит в каждом числе. 10101 010101 0010101 и т. Д. - все это одно и то же число (21), и как только оно будет преобразовано в число, невозможно будет определить, сколько начальных нулей было у исходного числа.

0 голосов
/ 27 августа 2018

так что проблема:
а равно 10 (в двоичном коде 0000 1010)
b равно 20 (в двоичном коде 0100 0100)
Вы хотите получить 2580 с использованием битового сдвига как-то.

если вы сдвинете вправо на 8 с помощью << = 8 (это то же самое, что умножить a на 2 ^ 8), вы получите <br>1010 0000 0000, что равно 10 * 2 ^ 8 = 2560.
, поскольку младшие биты всех равны 0 (когда вы используете <<, он заполняет новые биты 0), вы можете просто добавить b поверх него 1010 0000 0000 + 0100 0100, что дает 1010 0001 0100. <br>
так что в 1 строке кода это var result = a<<8 + b.

Помните, что в языках программирования большинство из них не имеют явных встроенных типов для «двоичного». Но все является двоичным по своей природе. так что int является «двоичным», объект - «двоичным» .... и т. д. Если вы хотите выполнить некоторые двоичные операции с некоторыми данными, вы можете просто использовать имеющийся у вас тип данных в качестве операндов для двоичных операций.

это более общий вариант объединения двоичных представлений двух чисел без использования строковых операций и данных 

/*
  
  This function concate b to the end of a and put 0's in between them.  
  
  b will be treated starting with it's first 1 as its most significant bit
  
  b needs to be bigger than 0, otherwise, Math.log2 will give -Infinity for 0 and NaN for negative b
  
  padding is the number of 0's to add at the end of a
*/

function concate_bits(a, b, padding) {

  //add the padding 0's to a
  a <<= padding;

  //this gets the largest power of 2
  var power_of_2 = Math.floor(Math.log2(b));
  var power_of_2_value;

  while (power_of_2 >= 0) {
    power_of_2_value = 2 ** power_of_2;
    a <<= 1;
    if (b >= power_of_2_value) {
      a += 1;
      b -= power_of_2_value;
    }
    power_of_2--;
  }
  return a;
}

//this will print 2580 as the result
let result = concate_bits(10, 20, 3);
console.log(result);
0 голосов
/ 26 августа 2018

Ваше основное уравнение: 

c = b + (a << 8).

Хитрость в том, что вам нужно всегда сдвигаться на 8. Но так как a и b не всегда используют все 8 битов в байте,JavaScript автоматически пропускает любые ведущие нули.Нам нужно восстановить число ведущих нулей (b) или конечных нулей a и добавить их обратно перед добавлением.Таким образом, все биты остаются на своих местах.Для этого требуется следующее уравнение: 

c = b + (a << s + r)

Где s - это самый высокий установленный бит (идущий справа налево) в b, а r - это оставшееся количество битов, такое что s + r = 8.

По сути, все, что вы делаете, это смещаете первый операнд a на 8 бит, чтобы эффективно добавить конечные нули к a или, в равной степени, дополняя ведущие нули вторым операндом b.Потом добавляешь нормально.Это может быть выполнено с использованием логарифмов, сдвига и побитовой операции OR, чтобы обеспечить решение O(1) для некоторых произвольных положительных целых чисел a и b, где число битов в aи b не превышают некоторое положительное целое число n.В случае байта n = 8. 

// Bitwise log base 2 in O(1) time
function log2(n) {

  // Check if n > 0

  let bits = 0;

  if (n > 0xffff) {
      n >>= 16;
      bits = 0x10;
  }

  if (n > 0xff) {
      n >>= 8;
      bits |= 0x8;
  }

  if (n > 0xf) {
      n >>= 4;
      bits |= 0x4;
  }

  if (n > 0x3) {
      n >>= 2;
      bits |= 0x2;
  }

  if (n > 0x1) {
      bits |= 0x1;
  }

  return bits;
}

// Computes the max set bit
// counting from the right to left starting
// at 0. For 20 (10100) we get bit # 4.
function msb(n) {

  n |= n >> 1;
  n |= n >> 2;
  n |= n >> 4;
  n |= n >> 8;
  n |= n >> 16;

  n = n + 1;

  // We take the log here because
  // n would otherwise be the largest
  // magnitude of base 2. So, for 20,
  // n+1 would be 16. Which, to 
  // find the number of bits to shift, we must 
  // take the log base 2
  return log2(n >> 1);
}

// Operands
let a = 0b00001010  // 10
let b = 0b00010100  // 20

// Max number of bits in
// in binary number
let n = 8

// Max set bit is the 16 bit, which is in position
// 4. We will need to pad 4 more zeros
let s = msb(b) 

// How many zeros to pad on the left
// 8 - 4 = 4
let r = Math.abs(n - s)

// Shift a over by the computed 
// number of bits including padded zeros
let c = b + (a << s + r)

console.log(c)

Вывод: 

2580

Примечания:

  • Это НЕ коммутативно.
  • Добавить проверку ошибок в log2 () для отрицательных чисел и других крайних случаев.

Ссылки:

...