Ruby/Python/C#からpopcountを呼ぶ


[CodeIQ 2812 「レッド・アンド・ホワイト」問題](https://codeiq.jp/q/2812)。問題の概要は[解説](https://codeiq.jp/magazine/2016/05/41263/)を参照していただくとして、要するに、`1<<popcount(n)`を出力すれば良い。
C言語で解くなら、

```c
n;main(){scanf("%d",&n);n=!printf("%d\n",1<<__builtin_popcount(n));}
```

となるが、この`__builtin_popcount`をC以外から呼ぶには一工夫必要になる。
調査の結果、Linuxでは`__sched_popcount()`、OSXでは`__popcountdi2()`が使えることが判明した。
`int __sched_popcount(size_t siz,long *a)`というシグネチャであるが、`(8,long long[1]{…})`を渡してもとりあえず動く。後者が、32bit環境では`int[2]{…}`と解釈され、__sched_popcountはその和を返すためである。

Ruby/Python/C#で、これらの関数を呼ぶには次にようにする。
なお、マジックナンバー8はできれば避けるべきものである。Pythonは`ctypes.sizeof(ctypes.c_long)`としているので最も正確である。

- [Ruby](http://ideone.com/ffgjbt)

```rb
#!/usr/bin/ruby
if RUBY_PLATFORM=~/linux/
	if true
		require 'fiddle'
		__popcount_fn=Fiddle::Function.new(Fiddle::Handle::DEFAULT['__sched_cpucount'],[Fiddle::TYPE_INT,Fiddle::TYPE_VOIDP],Fiddle::TYPE_INT)
		define_method(:popcount){|n|__popcount_fn.call(8,[n].pack('q'))}
	else
		require 'fiddle/import'
		module LibC
			extend Fiddle::Importer
			dlload 'libc.so.6'
			extern 'int __sched_cpucount(int,long long*)'
		end
		def popcount(n) LibC.__popcountdi2(8,[n]) end
	end
elsif RUBY_PLATFORM=~/darwin/
	if true
		require 'fiddle'
		__popcount_fn=Fiddle::Function.new(Fiddle::Handle::DEFAULT['__popcountdi2'],[Fiddle::TYPE_LONG],Fiddle::TYPE_INT)
		define_method(:popcount){|n|__popcount_fn.call(n)}
	else
		require 'fiddle/import'
		module LibC
			extend Fiddle::Importer
			dlload 'libSystem.dylib'
			extern 'int __popcountdi2(long)'
		end
		def popcount(n) LibC.__popcountdi2(n) end
	end
else
	def popcount(n) n==0 ? 0 : popcount(n/2)+n%2 end
end

p 1<<popcount(gets.to_i)
```

なお、CodeIQのRubyは1.9.3であるため、次のようにする。グローバル変数があるので汚いが、やむを得ない。

```rb
require 'fiddle'
require 'dl'
$__popcount_fn=Fiddle::Function.new(DL::Handle::DEFAULT['__sched_cpucount'],[Fiddle::TYPE_INT,Fiddle::TYPE_VOIDP],Fiddle::TYPE_INT)
def popcount(n) $__popcount_fn.call(8,[n].pack('q')) end
```

- [Python](http://ideone.com/4DBkKM)

```py
#!/usr/bin/python
import sys,ctypes
if sys.version_info[0]>=3:
	raw_input=input
	xrange=range

if sys.platform.startswith('linux'):
	libc=ctypes.cdll.LoadLibrary('libc.so.6')
	popcount=lambda n:libc.__sched_cpucount(ctypes.sizeof(ctypes.c_long),(ctypes.c_long*1)(n))
elif sys.platform=='darwin':
	libc=ctypes.cdll.LoadLibrary('libSystem.dylib')
	popcount=lambda n:libc.__popcountdi2(n)
else:
	popcount=lambda n:0 if n==0 else popcount(n/2)+n%2

print(1<<popcount(int(raw_input())))
```

- [C#](http://ideone.com/HTYKpR)

```
using System;
using System.Runtime.InteropServices;
 
class CodeIQ2812{
	[DllImport("msvcrt",CallingConvention=CallingConvention.Cdecl)]static extern int __popcountdi2(long n);
	[DllImport("msvcrt",CallingConvention=CallingConvention.Cdecl)]static extern int __sched_cpucount(int n, long[] a);

	static int popcount(long n){
		//コンパイル時に判別する手段がないので適切にコメントアウトすること
		//return __popcountdi2(n);
		return __sched_cpucount(8,new long[]{n});
		//return n==0 ? 0 : popcount(n/2)+(int)(n%2);
	}
	static void Main(){
		int n=int.Parse(Console.ReadLine());
		Console.WriteLine(1<<popcount(n));
	}
}
```

- 最後に

マーシャリングのオーバーヘッドのほうが大きい場合があるのではないかと思った方、多分当たりです。この方法のご利用は計画的に。