スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

F#雑記 オンになっているビットの数を数える

オンになっているビットの数を数えるのは例えば次の様にできます。
(とりあえず対象はbyte型にしておきます。(論理シフトなので安全))
 
> let isLowestBitOn (n: byte)= 
    ((n >>> 1) <<< 1) <> n ;;
 
val isLowestBitOn : byte -> bool
 
> let bitCount00 (m:byte) =
    let rec subCount step sum n =
         if step = 8 then sum
         else
            let dif = if isLowestBitOn n then 1
                      else 0
            subCount (step+1) (sum + dif) (n >>> 1)        
    subCount 0 0 m;;
 
val bitCount00 : byte -> int
 
(使用例)
> bitCount00 0b10111111uy;;
val it : int = 7
 
次はzeclさんの記事を参考にさせて頂いて上とは別の実装をしてみたいと思います。
 
まずは2ビットのみを考えます。
ビットのパターンと立っているビットの数は次のようになります。
 
00 -> 0
01 -> 1
10 -> 1
11 -> 2
 
次にこれを右に一つずらしたものを元の数から引くとどうなるかを考えます。
  
00 -> 00 - 00 -> 00(数として0)
01 -> 01 - 00 -> 01(数として1)
10 -> 10 - 01 -> 01(数として1)
11 -> 11 - 01 -> 10(数として2)
 
ということで右に一つシフトしてもとの数から引いてその2ビットを数として考えると立っているビット数を得ることができます。
 
次に4ビットの場合ですが、単に右にずらしてもとの数から引くと次のようになります。
(2ビット毎に分けて考えるため、間にスペースを入れて示してます。)

11 11 -> 11 11 - 01 11 -> 10 00 (上の2ビットは数として2なので合っているが、下の2ビットが数として0となって合っていない)
これは上のビットからのシフト分が下の2ビットにも影響を与えているせいです。
そこで次のようにワンクッション入れます。
11 11 -> 11 11 - ((01 11) &&& (01 01)) -> 11 11 - 01 01 -> 10 10
&&& (01 01)の部分で、上のビットの繰り下がりが下に影響しないようにマスクを入れています。
では同様の考え方で8ビットでやってみます。

11 01 10 00 -> 11 01 10 00 - ((01 10 11 00) &&& (01 01 01 01)) = 11 01 10 00 - 01 00 01 00 =
10 01 01 00 
 2  1  1  0 (2ビット毎の数として) 
 
あとはこれを隣接する2ブロック毎の和にします。
「0011 0011 でマスクしたもの」と「1100 1100でマスクして2ビット右にシフトしたもの」を加えます。
1001 0100 ->
((1001 0100) &&& (0011 0011)) + (((1001 0100) &&& (1100 1100)) >>> 2) =
0001 0000 + ((1000 0100) >>> 2) =
0001 0000 + 0010 0001 =
0011 0001
   3    1 (4ビット毎の数として)
あとはもう一段階で終わりです。
「0000 1111 でマスクしたもの」と「4ビット右にシフトしたもの(上がないのでマスクの必要なし)」を加えます。
0011 0001 ->
((0011 0001) &&& (0000 1111)) + ((0011 0001) >>> 4) =
0000 0001 + 0000 0011 =
000 0100
       4 (8ビット全体の数として)
 
では定義してみます。
 
> let bitCountByte (m : byte) =
    m
    |> (fun x -> x - ((x>>>1) &&& 0b01010101uy))
    |> (fun x -> (x &&& 0b00110011uy) + ((x &&& 0b11001100uy) >>> 2))
    |> (fun x -> (x &&& 0b00001111uy) + (x >>> 4));;
 
val bitCountByte : byte -> byte
 
使ってみます。
 
> bitCountByte  0b10111111uy;;
val it : byte = 7uy
> bitCountByte  0b10000001uy;;
val it : byte = 2uy
 
かつてブログ
 
> strBit  '■' '□' 3uy;; 
val it : string = "□□□□□□■■" 
  
> strBit  '■' '□' 8uy;; 
val it : string = "□□□□■□□□" 
 
というように視覚化できる関数を書いたのでこれを使ってどのようになっているかを視覚化してみたいと思います。
 
> let bitDispSub (s:string) (m:byte) =
    printfn "%s : %s" (strBit '■' '□' m) s
    m
 
let bitCountByteDisp (m : byte) =
    m
    |> (fun x -> bitDispSub  "元の数" x)
    |> (fun x -> x - ((x>>>1) &&& 0b01010101uy))
    |> (fun x -> bitDispSub "2ビット毎のオンになっているビット数" x)
    |> (fun x -> (x &&& 0b00110011uy) + ((x &&& 0b11001100uy) >>> 2))
    |> (fun x -> bitDispSub "4ビット毎のオンになっているビット数"x)
    |> (fun x -> (x &&& 0b00001111uy) + (x >>> 4))
    |> (fun x -> bitDispSub "全体のオンになっているビット数" x);;
 
val bitDispSub : string -> byte -> byte
val bitCountByteDisp : byte -> byte
 
(使用例)
 
> bitCountByteDisp  0b10111111uy;;
■□■■■■■■ : 元の数
□■■□■□■□ : 2ビット毎のオンになっているビット数
□□■■□■□□ : 4ビット毎のオンになっているビット数
□□□□□■■■ : 全体のオンになっているビット数
val it : byte = 7uy
 
> bitCountByteDisp  0b11011010uy;;
■■□■■□■□ : 元の数
■□□■□■□■ : 2ビット毎のオンになっているビット数
□□■■□□■□ : 4ビット毎のオンになっているビット数
□□□□□■□■ : 全体のオンになっているビット数
val it : byte = 5uy
 
ではuint32版を定義しておきます。
 
> let bitCountUint32 (n : uint32) =
    n
    |> (fun x -> x - ((x>>>1) &&& 0b01010101010101010101010101010101u))
    |> (fun x -> (x &&& 0b00110011001100110011001100110011u) + ((x &&& 0b11001100110011001100110011001100u) >>> 2))
    |> (fun x -> (x &&& 0b00001111000011110000111100001111u) + ((x &&& 0b11110000111100001111000011110000u) >>> 4))
    |> (fun x -> (x &&& 0b00000000111111110000000011111111u) + ((x &&& 0b11111111000000001111111100000000u) >>> 8))
    |> (fun x -> (x &&& 0b00000000000000001111111111111111u) + (x >>> 16))
;;
 
val bitCountUint32 : uint32 -> uint32
 
(使用例)
 
> bitCountUint32 8u;;
val it : uint32 = 1u
 
> bitCountUint32 7u;;
val it : uint32 = 3u
 
> bitCountUint32 256u;;
val it : uint32 = 1u
 
> bitCountUint32 (System.UInt32.MaxValue);;
val it : uint32 = 32u
スポンサーサイト

テーマ : プログラミング
ジャンル : コンピュータ

コメントの投稿

非公開コメント

訊いてもイイですか?

isLowestBitOn で、&&&(論理積)を使わずに、シフト2回でやっているのはなぜですか?
何か意味がありますか?
isHighestBitOn なんかは、C のようなint のサイズが決まらないような言語なら、
こういうのは意味があるかなと思うんですが・・

No title

すいません、単なる直し忘れです。(その時はそれしか思いつかなかった。)ここ2、3日は「コンパイラ インタプリタ開発」なる本(BLUEPIXYさんもレビューされてましたが)を読んで、再帰下向き構文解析なるものを勉強してました。(もの知らずな輩です。もっと修行せねば。)
プロフィール

T GYOUTEN

Author:T GYOUTEN
F#と英単語とフリーソフトと読書に興味があります。
ホームページでフリーソフトも公開しています。どぞ御贔屓に。

最新記事
最新コメント
最新トラックバック
月別アーカイブ
カテゴリ
フリーエリア
フリーエリア
blogram投票ボタン
検索フォーム
RSSリンクの表示
リンク
ブロとも申請フォーム

この人とブロともになる

QRコード
QRコード
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。