PopCnt

仕事でintのビット数を数える処理が必要になった。
SSE4あたりではPOPCNTがあるらしいが、そんな新しいCPUとかコンパイラはつかってないのでどんなアルゴリズムがあるか調べてみた。
こんなのがあって

int popcnt1(unsigned int val){
    unsigned int bits = val;
    bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);
    bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);
    bits = (bits & 0x0F0F0F0F) + (bits >> 4 & 0x0F0F0F0F);
    bits = (bits & 0x00FF00FF) + (bits >> 8 & 0x00FF00FF);
    bits = (bits & 0x0000FFFF) + (bits >>16 & 0x0000FFFF);
    return bits;
}

これも同じ

int popcnt2(unsigned int val){
    unsigned int bits = val;
    bits = ((bits & 0xAAAAAAAA) >>  1) + (bits & 0x55555555);
	bits = ((bits & 0xCCCCCCCC) >>  2) + (bits & 0x33333333);
	bits = ((bits & 0xF0F0F0F0) >>  4) + (bits & 0x0F0F0F0F);
	bits = ((bits & 0xFF00FF00) >>  8) + (bits & 0x00FF00FF);
	bits = ((bits & 0xFFFF0000) >> 16) + (bits & 0x0000FFFF);
	return bits;
}

アイディアというか考え方はどちらも同じ。
この例だと32bitを2bit毎に足して、結果をその2bit内にためておく。つぎに2bitの結果を2個足して、結果を4bit内にためておく。さらに4bitの結果を2個足して、結果を8bit内にためておく...と続くと。

2bitのデータnのPOPCNTは

popcnt=(n&0b1)+(n>>1&0b1)
n=0のとき00&01+00&01=0
n=1のとき01&01+00&01=1
n=2のとき10&01+01&01=1
n=3のとき11&01+01&01=2

4bitのデータnのPOPCNTは

n1=(n&0b0101)+(n>>1&0b0101)
popcnt=(n1&0b0011)+(n1>>2&0b0011)

n=1のときn1=1+0=1,popcnt=1+0=1
n=2のときn1=0+1=1,popcnt=1+0=1
n=3のときn1=1+1=2,popcnt=1+1=2
n=4のときn1=4+0=1,popcnt=0+1=1
n=5のときn1=5+0=1,popcnt=1+1=2
n=6のときn1=4+1=5,popcnt=1+1=2
n=7のときn1=5+1=6,popcnt=1+2=3
以下続く...

Hashタプル

復習のつもりでついでに予習
7.6あたりの['name', 'rwiki' nil]は['name', 'rwiki', nil]ですね。

階乗サーバーのHashタプル版のnotifyはこんなの

require 'drb/drb'
require 'multiplenotify'

ts_uri = ARGV.shift || 'druby://localhost:12345'
DRb.start_service
$ts = DRbObject.new_with_uri(ts_uri)
mn = MultipleNotify.new($ts, nil, [{"request"=>"fact", "range"=>Range}, \
{"answer"=>"fact", "range"=>Range,  "fact"=>Integer}])

while true
  e,t = mn.pop, Time.now
  p t, e
end

バリア同期

復習。
barrier.rb

class Barrier
  def initialize(ts, n, name=nil)
    @ts = ts
    @name = name || self
    @ts.write([key,n])
  end
  def key
    @name
  end
  def sync
    tmp, val = @ts.take([key,nil])
    @ts.write([key, val - 1])
    @ts.read([key, 0])
  end
end

TupleSpaceをつくるほう、5個で待ち合わせる。

require 'barrier.rb'
require 'rinda/tuplespace'
$ts = Rinda::TupleSpace.new
$barrier = Barrier.new( $ts, 5, "test_barrier")
DRb.start_service('druby://localhost:12345', $barrier )
DRb.thread.join

お仕事して待ち合わせるほう

require 'drb/drb'
require 'barrier'
DRb.start_service
$ts = DRbObject.new_with_uri('druby://localhost:12345')
$ts.sync

このスクリプトの5個目が実行されると、それまでの4つもふくめて解放されるのね。

9.10

Ubuntu 9.10がリリースされたので、早速アップグレードしてみた。
いつもどおり(?)hgfsによるホストとの共有フォルダが見えなくなった。
open-vm-toolsのコンパイル(http://d.hatena.ne.jp/you-ssk/20091027/1256649892)もできなくなった...
困ったよ、と思いつつVMWare　Player3.0についてきていたVMWareToolsがあったので、open-vm-toolsを削除してVMWareToolsを入れてみた。
これで共有フォルダが見えるようになった。ふぅ〜。

Ubuntu open-vm-tools

VMWare PlayerでUbuntu9.04を使っているのだけど、いつのまにかホストとの共有フォルダが見えなくなっている。
たしか8月にも、そんなことがあって以下を参考にモジュールをコンパイルしなおして解決した。

http://omake.accense.com/wiki/VMwareUbuntu9.04

今回、すっかり直し方を忘れていたのでメモっとく。