トップ 差分 一覧 ソース 検索 ヘルプ RSS ログイン

二進展開(MSB/LSB)

[アルゴリズム]

二進展開(MSB/LSB)

  概要

  • Man page of FFS
    • ワード i の中で最初にセットされている (最下位)ビットの位置を返す

  各言語での実装

Rubyでテスト

  • 1~20までのLSBとその2進数表記を出力してみる
def msb(x)
  x.to_s(2).size - 1
end
 
def lsb(x)
  msb(x & -x)
end

puts "n\tn as bin\tLSB(n)\tLSB(n) as binary"
for i in 1..20
    puts "#{i}\t#{i.to_s(2).rjust(8, '0')}\t#{lsb(i)+1}\t#{(lsb(i)+1).to_s(2).rjust(8, '0')}"
end
  • 各要素のLSB(Least SIgnificant Bit)は?
    • 2進数で表現したときはじめて「1」が来るのは右から何番目?
    • 注意:上記の関数は0-indexedなので、+1したほうがよさそう

LSB(n)の値が、インデックスnの階層をそのまま表している。

n	n as bin	LSB(n)	LSB(n) as binary
1	00000001	1	00000001
2	00000010	2	00000010
3	00000011	1	00000001
4	00000100	3	00000011
5	00000101	1	00000001
6	00000110	2	00000010
7	00000111	1	00000001
8	00001000	4	00000100
9	00001001	1	00000001
10	00001010	2	00000010
11	00001011	1	00000001
12	00001100	3	00000011
13	00001101	1	00000001
14	00001110	2	00000010
15	00001111	1	00000001
16	00010000	5	00000101
17	00010001	1	00000001
18	00010010	2	00000010
19	00010011	1	00000001
20	00010100	3	00000011
お名前: コメント: