「ハッカーのたのしみ」はかなりの良書。いまさらFlagsAttributeのレシピ、リターンズ。.NET FrameworkにBitCountくらい標準であってもいいのにね
以前、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:私はなぜか、「ハッカーのたしなみ」と空目します。