読者です 読者をやめる 読者になる 読者になる
ようこそ。睡眠不足なプログラマのチラ裏です。

「ハッカーのたのしみ」はかなりの良書。いまさらFlagsAttributeのレシピ、リターンズ。.NET FrameworkにBitCountくらい標準であってもいいのにね

プログラミング アルゴリズム Java F# C# VB.NET

以前、FlagsAttributeとビット演算のちょっとしたレシピという記事を書きました。
ご覧頂くとわかるように、とてもダサい実装になっています。記事を掲載してすぐに知人からツッコミがありました。
ツッコミがあったときにすぐに続編記事を書いて訂正しようと思っていたのですが、すっかり忘れていました。
最近でも、いまだに「FlagsAttribute」を検索ワードとして、こちらにたどり着く方も多いようなので、
このままダサい実装を晒し続けて、そのまま参考にされるのはとても心が痛みます。
なので、ダサくない実装をF#、C#VB.NETの3つの言語で掲載しておこうと思います。


とある知人からの指摘

ブログのFlagsAttributeの記事みたけど、たしかにアレはださすぎるw
BitCountやりたいなら、常識的に考えてビット演算で。Javaの実装とかモロだから参考にするとよいよ。
あと、ビット演算関係では、「ハッカーのたのしみ」って本にいろいろ面白いこと載ってるから読んどいた方がいい。

というような感じでした。そうかー、Javaには標準であるのね。
その後、早速Javaの実装を見たり、「ハッカーのたのしみ」という本を読みました。*1


ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか

ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか

  • 作者: ジュニア,ヘンリー・S.ウォーレン,Jr.,Henry S. Warren,滝沢徹,玉井浩,鈴木貢,赤池英夫,葛毅,藤波順久
  • 出版社/メーカー: エスアイビーアクセス
  • 発売日: 2004/09
  • メディア: 単行本
  • 購入: 35人 クリック: 732回
  • この商品を含むブログ (127件) を見る



JavaのbitCountの実装はこんな感じになっている

Javaの Integer.bitCount( i ) という
intの1のビットの数を数えるメソッドの実装は、こんな感じになっているようです。

public static int bitCount(int i) {
        i = i - ((i >>> 1) & 0x55555555);
        i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
        i = (i + (i >>> 4)) & 0x0f0f0f0f;
        i = i + (i >>> 8);
        i = i + (i >>> 16);
        return i & 0x3f;
    }


このような実装で、結果的に1のビットの立つ数を計算することができる、と。


一見意味不明のプログラムに見えますが、コードと向きあってちゃんと読めば、それほど難しいことはしていません。
これはいわゆる分割統治を用いたアルゴリズムで、まず2ビットごとに分割した16のブロックに
元々あった2つのビットの和をセットし、次に隣接する2つのブロックの和を計算し、
その結果をまた、4ビットごとに分割された8ブロックにそれぞれ結果をセットする。
といった操作を繰り返すことで、結果的に1のビットの数を数えています。
また、ブロックごとの和が隣接するブロックに影響を与えないのであればビット演算andは不要となることも
上記のコードは示しているというわけです。んー、なるほど。確かに無駄の少ない良質な実装ですね。


と、理屈はわかったのでのですが、
こういう発想は、ビット演算とは無縁に近いプログラミングライフを送っている自分には、
とても思い浮かばなかった。へっぽこプログラマであることを、再確認しました。


ググってみたところ、.NETでこの手の話を書いているひとは、なぜかいらっしゃらないようでした。
ということで、.NETにおけるBitCountの実装サンプルおよび、
FlagsAttributeのレシピを、F#、C#VB.NETで書きましたので置いておきます。


F#による実装

namespace Library1

[<System.Runtime.CompilerServices.ExtensionAttribute>]
module public EnumFlagsExtentions =
    open System
    open System.Runtime.CompilerServices

    ///intについてビットが立っている数を取得します。
    [<Extension>]
    let BitCount (self : int) = 
      self |> fun x -> x - ((x >>> 1) &&& 0x55555555)
           |> fun x -> ((x >>> 2) &&& 0x33333333) + (x &&& 0x33333333)
           |> fun x -> (x >>> 4) + x &&& 0x0f0f0f0f
           |> fun x -> (x >>> 8) + x
           |> fun x -> (x >>> 16) + x &&& 0x3f

    ///FlagsAttribute属性が付加されたenumについて、ビットが立っている数を取得します。
    [<Extension>]
    let FlagsCount<'T when 'T: enum<int>> (self : 'T) = 
      if not(self.GetType().IsEnum) then
        raise (new ArgumentException("enumじゃなきゃだめ"))
      if not(Attribute.IsDefined(self.GetType(),typeof<FlagsAttribute>)) then
        raise (new ArgumentException("FlagsAttrebute属性ついてなきゃだめ"))
      self |> Convert.ToInt32 
           |> BitCount

    ///FlagsAttribute属性が付加されたenumについて、ビットが立っているenumの要素を取得します。
    [<Extension>]
    let GetFlags<'T when 'T: enum<int>> (self : 'T) = 
      if not(self.GetType().IsEnum) then
        raise (new ArgumentException("enumじゃなきゃだめ"))
      if not(Attribute.IsDefined(self.GetType(),typeof<FlagsAttribute>)) then
        raise (new ArgumentException("FlagsAttrebute属性ついてなきゃだめ"))
      let target = self |> Convert.ToInt32
      seq{for i in 0..31 do 
           let bit x i = 
             let x = target >>> i 
             let x = x &&& - x
             x
           let x = bit target i
           if (x = 0b1) then
             yield x <<< i :> obj :?> 'T
         }

F#では、ジェネリックの制約にenum型を指定することができます。素晴らしいです。
ですので、通常F#で利用する分には、「self.GetType().IsEnum」によるチェックをする必要はありませんが、
C#VB.NETでは、enum型によるジェネリックの制約は利用できないので、
C#VB.NETから利用されることも考慮するのであれば、このように実装しておくことが望ましいでしょう。
また、Extension属性を付加することで、C#VB.NETから利用したときに、ちゃんと拡張メソッドとして機能します。


お試し

namespace ConsoleApplication1
open Library1

module Test =
    open System
    open Library1.EnumFlagsExtentions 

    [<Flags()>]
    type EDocks =
     | None   = 0b00000
     | Top    = 0b00001 
     | Left   = 0b00010
     | Right  = 0b00100
     | Bottom = 0b01000
     | All    = 0b01111

    let enum0 = EDocks.Non
    let enum1 = EDocks.Top
    let enum2 = EDocks.Top ||| EDocks.Left
    let enum3 = EDocks.Top ||| EDocks.Left ||| EDocks.Right 
    let enum4 = EDocks.Top ||| EDocks.Left ||| EDocks.Right ||| EDocks.Bottom 
    let enum5 = EDocks.Non ||| EDocks.Left ||| EDocks.Left  ||| EDocks.Non

  
    let _ =
      Console.WriteLine(enum0 |> FlagsCount)
      Console.WriteLine(enum1 |> FlagsCount) 
      Console.WriteLine(enum2 |> FlagsCount) 
      Console.WriteLine(enum3 |> FlagsCount) 
      Console.WriteLine(enum4 |> FlagsCount) 
      Console.WriteLine(enum5 |> FlagsCount)
      enum2 |> GetFlags |> Seq.iter Console.WriteLine
      Console.WriteLine ()
      enum4 |> GetFlags |> Seq.iter Console.WriteLine
      (-90000000) |> BitCount |> Console.WriteLine 
      Console.ReadKey()

F#では、FlagsAttributeを付加したenum型を記述する際、
「0b00100」のようにビットで記述することができます。これは直感的に書けてとても便利ですね。


実行結果

0
1
2
3
4
1
Top
Left

Top
Left
Right
Bottom
15


C#による実装

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ClassLibrary1
{
    public static class EnumFlagsExtentions
    {
        /// <summary>
        /// intについてビットが立っている数を取得します。
        /// </summary>
        /// <param name="self"></param>
        /// <returns></returns>
        public static int BitCount(this int self)
        {
            var x = self - ((self >> 1) & 0x55555555);
            x = ((x >> 2) & 0x33333333) + (x & 0x33333333);
            x = (x >> 4) + x & 0x0f0f0f0f;
            x += x >> 8;
            return (x >> 16) + x & 0xff;
        }

        /// <summary>
        /// FlagsAttribute属性が付加されたenumについて、ビットが立っている数を取得します。
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="self"></param>
        /// <returns></returns>
        public static int FlagsCount<T>(this T self) where T : struct, IConvertible 
        {
            if (!self.GetType().IsEnum)
                throw new ArgumentException("enumじゃなきゃだめ");
            if (!Attribute.IsDefined(self.GetType(), typeof(FlagsAttribute)))
                throw new ArgumentException("FlagsAttrebute属性ついてなきゃだめ");
            return BitCount(Convert.ToInt32(self));
        }

        /// <summary>
        /// FlagsAttribute属性が付加されたenumについて、ビットが立っているenumの要素を取得します。
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="self"></param>
        /// <returns></returns>
        public static IEnumerable<T> GetFlags<T>(this T self) where T : struct, IConvertible 
        {
            if (!self.GetType().IsEnum)
                throw new ArgumentException("enumじゃなきゃだめ");
            if (!Attribute.IsDefined(self.GetType(), typeof(FlagsAttribute)))
                throw new ArgumentException("FlagsAttrebute属性ついてなきゃだめ");

            var target = Convert.ToInt32(self);
            for (int i = 0; i < 32; i++)
            {
                var x = target >> i;
                x &= -x;
                if (x == 0x0001)
                    yield return (T)Enum.ToObject(typeof(T), x << i);
            }
        }
    }
}


VB.NETによる実装

Imports System.Runtime.CompilerServices

Public Module EnumFlagsExtentions

    ''' <summary>
    ''' Integerについてビットが立っている数を取得します。
    ''' </summary>
    ''' <param name="self"></param>
    ''' <returns></returns>
    ''' <remarks></remarks>
    <Extension()> _
    Public Function BitCount(ByVal self As Integer) As Integer
        Dim x As Integer = self - ((self >> 1) And &H55555555)
        x = ((x >> 2) And &H33333333) + (x And &H33333333)
        x = (x >> 4) + x And &HF0F0F0F
        x += x >> 8
        Return (x >> 16) + x And &HFF
    End Function

    ''' <summary>
    ''' FlagsAttribute属性が付加されたenumについて、ビットが立っている数を取得します。
    ''' </summary>
    ''' <typeparam name="T"></typeparam>
    ''' <param name="self"></param>
    ''' <returns></returns>
    ''' <remarks></remarks>
    <Extension()> _
    Public Function FlagsCount(Of T As Structure)(ByVal self As T)
        If Not self.GetType().IsEnum Then
            Throw New ArgumentException("enumじゃなきゃだめ")
        End If
        If Not Attribute.IsDefined(self.GetType(), GetType(FlagsAttribute)) Then
            Throw New ArgumentException("FlagsAttrebute属性ついてなきゃだめ")
        End If
        Return BitCount(Convert.ToInt32(self))
    End Function

    ''' <summary>
    ''' FlagsAttribute属性が付加されたenumについて、ビットが立っているenumの要素を取得します。
    ''' </summary>
    ''' <typeparam name="T"></typeparam>
    ''' <param name="self"></param>
    ''' <returns></returns>
    ''' <remarks></remarks>
    <Extension()> _
    Public Function GetFlags(Of T As Structure)(ByVal self As T) As IEnumerable(Of T)
        If Not self.GetType().IsEnum Then
            Throw New ArgumentException("enumじゃなきゃだめ")
        End If
        If Not Attribute.IsDefined(self.GetType(), GetType(FlagsAttribute)) Then
            Throw New ArgumentException("FlagsAttrebute属性ついてなきゃだめ")
        End If
        Dim target As Integer = Convert.ToInt32(self)
        Dim result As New List(Of T)()
        For i As Integer = 0 To 31
            Dim x As Integer = target >> i
            x = x And -x
            If x = &H1 Then
                result.Add(DirectCast([Enum].ToObject(GetType(T), x << i), T))
            End If
        Next
        Return result
    End Function

End Module


.NET4が使えるのならば、C#VB.NETではCode Contractsが利用できるので、「契約」を用いて
事前条件でenum型であるかどうか、FlagsAttribute属性が付加されているかどうかについて
判定することができればより良い実装にできるのではないかと検討してみたのですが、残念ながらできないようです。
このあたりのメタ的要素の判定についても「契約」で表現でるようになってくれると、
Code Contractsの利用価値が更に高まると思うのですが。これについては今後に期待したいところです。


最後に
というわけで、ダサい実装をやっと訂正できました。


複数のbool(Boolean)値を一度に扱うような場合、FlagsAttributeを付加したenumは利用価値が高いことも多いです。
なので、このようなレシピは是非手持ちのクラスライブラリに忍ばせておきたいところです。
余裕があれば、他にJavaで標準でサポートされているInteger.Reverseや
Integer.HighestOneBit、Integer.LowestOneBitなどのメソッドについても実装しておくと嬉しいかもしれません。
それはそうと、C#VB.NETでもF#と同様に、ジェネリック制約にenum型が使えるようにしてもらいたいものです。

*1:私はなぜか、「ハッカーのたしなみ」と空目します。