gotin blog

Whatever gotin wanna write

割り算 by bit演算メモ

bit演算なんてもう何年もやっておらず、ふと練習したメモ。

var LEFTBIT = 1 << 30;
function divide(n, div){
  var t = 0;
  var result = 0;
  var mbit = LEFTBIT;
  while(mbit > 0){
    result = result << 1;
    t = t << 1;
    var x = n & mbit;
    t += x ? 1:0;
    var tmp = t -div;
    if(tmp >= 0){
      result += 1;
      t = tmp;
    }
    mbit = mbit >>> 1;
  }
  return [result, t];
}
divide(33, 7); // [4,5]
divide(2, 7); // [0,2]

n,divが負の値の場合の考慮も入れないと。

javascriptだと負の数はどう表現されているんだろう

var LEFTBIT = 1 << 30;
function int2bitstring(n){
  var buf = [];
  for(var mbit = LEFTBIT;mbit > 0; mbit = mbit >>> 1){
    buf.push((n & mbit) > 0 ? 1 : 0);
  }
  return buf.join("");
}

int2bitstring(-1); //"1111111111111111111111111111111"
int2bitstring(-2); //"1111111111111111111111111111110"
int2bitstring(-256); //"1111111111111111111111100000000"

おそらく、左端のbitが0か1かで正負を表していて、負であれば
反転して1を足して表現される数の-1倍したもの、を表現するという方法だと想像。

あ、でもどう表現されているかは知らなくてもいいか

var LEFTBIT = 1 << 30;
function divide(n, div){
  var minus = false;
  if(n < 0){
    minus = !minus;
    n = -n;
  }
  if(div < 0){
    minus = !minus;
    div = -div;
  }
  var t = 0;
  var result = 0;
  var mbit = LEFTBIT;
  while(mbit > 0){
    result = result << 1;
    t = t << 1;
    var x = n & mbit;
    t += x ? 1:0;
    var tmp = t -div;
    if(tmp >= 0){
      result += 1;
      t = tmp;
    }
    mbit = mbit >>> 1;
  }
  return [(minus ? -result : result), t];
}
divide(-33, 7); // [-4,5]
divide(33, -7); // [-4,5]
divide(-33, -7); // [4,5]

bit表現してくれる関数とか普通にありそうだな。あと負の数の表現方法もきっと仕様書に書いてあるに違いない。

↑それ toString(2)でできるよ、と思ったんだけど、
(-2).toString(2)
の結果は
"-10"
ずるいよそれ(笑)

wikipediaより

符号付数値表現 - Wikipedia

2の補数表現を使ってるってことですね。学生の頃勉強してた気がするけどもう忘れちゃってるわぁ。

あと

0割もちゃんとエラーだすとかしないと。まぁいいや。