Выразить побитовое и (a & b) через десятичную арифметку

#математика #логика

Существует ли способ выразить операцию побитовое И через арифметические действия
(+,-,*,/,** и проч.)? 
    

Ответы

Ответ 1

Да. 

a & b = a0*b0 * 2^0 + a1*b1 * 2^1 + ... + aN * bN * 2^N


Где ai - i-й бит a, bi - i-й бит b


Ответ 2

Небольшой пример в дополнение к ответу @mnv
Суть побитового И - поразрядное умножение двоичных чисел. Но так как обычно используются
десятичные числа, то их необходимо перевести в двоичные.
Можно рассмотреть пример перевода числа 6 в двоичную форму



6 в двоичной системе представляется как 110. На рисунке видно, что это соответствует
остаткам от деления, причем разряды получаются от младшего к старшим.

Таким образом можно сформулировать следующий алгоритм:


разделить каждое из чисел на 2, деление целочисленное, если хотя бы один из результатов
0 - можно не продолжать, так как умножение на 0 равно 0.
взять остатки отделения, перемножить между собой - получим конкретное значение бита,
умножив это значение на 2i, где i номер итерации
вернуться к первому пункту с результатами деления.


Пример реализации: 



function calc(a, b) {
  var res = 0;
  for (var i = 0, c = a, d = b; c / 2 != 0 && d / 2 != 0; i++) {
    res += c % 2 * d % 2 * Math.pow(2, i); // получаем остатки от деления, умножаем
на степень двойки
    c = Math.floor(c / 2); // получаем целую часть от деления
    d = Math.floor(d / 2); // получаем целую часть от деления
  }
  
  document.getElementById('r').innerHTML = `bitwise &: ${a} & ${b} = ${a&b} 

Math: ${a} & ${b} = ${res}`;
}