2014/09/21(Sun)VC++ で __builtin_ctz __builtin_clz __builtin_popcount

はてブ数 2014/09/21 14:33 計算機な日記::プロコン つーさ

をするための intrin wrapper。

コンテストではローカルがVisualStudioで、ジャッジサーバはgccなので、
これを書いておくと、あまりその辺気を使わずビット演算できる


//// bit ////
#ifdef _MSC_VER
#ifdef _WIN32
inline unsigned int __builtin_ctz(unsigned int x) { unsigned long r; _BitScanForward(&r, x); return r; }
inline unsigned int __builtin_clz(unsigned int x) { unsigned long r; _BitScanReverse(&r, x); return 31 - r; }
inline unsigned int __builtin_ffs(unsigned int x) { unsigned long r; return _BitScanForward(&r, x) ? r + 1 : 0; }
inline unsigned int __builtin_popcount(unsigned int x){ return __popcnt(x); }
#ifdef _WIN64
inline unsigned long long __builtin_ctzll(unsigned long long x) { unsigned long r; _BitScanForward64(&r, x); return r; }
inline unsigned long long __builtin_clzll(unsigned long long x) { unsigned long r; _BitScanReverse64(&r, x); return 63 - r; }
inline unsigned long long __builtin_ffsll(unsigned long long x) { unsigned long r; return _BitScanForward64(&r, x) ? r + 1 : 0; }
inline unsigned long long __builtin_popcountll(unsigned long long x) { return __popcnt64(x); }
#else
inline unsigned int hidword(unsigned long long x) { return static_cast<unsigned int>(x >> 32); }
inline unsigned int lodword(unsigned long long x) { return static_cast<unsigned int>(x & 0xFFFFFFFF); }
inline unsigned long long __builtin_ctzll(unsigned long long x) { return lodword(x) ? __builtin_ctz(lodword(x)) : __builtin_ctz(hidword(x)) + 32; }
inline unsigned long long __builtin_clzll(unsigned long long x) { return hidword(x) ? __builtin_clz(hidword(x)) : __builtin_clz(lodword(x)) + 32; }
inline unsigned long long __builtin_ffsll(unsigned long long x) { return lodword(x) ? __builtin_ffs(lodword(x)) : hidword(x) ? __builtin_ffs(hidword(x)) + 32 : 0; }
inline unsigned long long __builtin_popcountll(unsigned long long x) { return __builtin_popcount(lodword(x)) + __builtin_popcount(hidword(x)); }
#endif // _WIN64
#endif // _WIN32
#endif // _MSC_VER

inline unsigned int bsf(unsigned int v) { return __builtin_ctz(v); } // 最下位の1は下から数えて何ビットめか?
inline unsigned long long bsf(unsigned long long v) { return __builtin_ctzll(v); } // 最下位の1は下から数えて何ビットめか?
inline unsigned int bsr(unsigned int v) { return 31 - __builtin_clz(v); } // 最上位の1は下から数えて何ビットめか?
inline unsigned long long bsr(unsigned long long v) { return 63 - __builtin_clzll(v); } // 最上位の1は下から数えて何ビットめか?
inline unsigned int msb(unsigned int v) { return 1 << bsr(v); } // 最上位の1だけ残す
inline unsigned long long msb(unsigned long long v) { return 1ull << bsr(v); } // 最上位の1だけ残す
inline unsigned int lsb(unsigned int v) { return v & -v; } // 最下位の1だけ残す
inline unsigned long long lsb(unsigned long long v) { return v & -v; } // 最下位の1だけ残す
inline unsigned int pop_lsb(unsigned int v) { return v & v - 1; } // 最下位の1以外を残す
inline unsigned long long pop_lsb(unsigned long long v) { return v & v - 1; } // 最下位の1以外を残す
inline unsigned int round_up_pow2(unsigned int v) { return msb(v - 1) << 1; } // 2の累乗に切り上げ
inline unsigned long long round_up_pow2(unsigned long long v) { return msb(v - 1) << 1; } // 2の累乗に切り上げ

// bit permutation。nビット立っているものを列挙する
inline unsigned int next_bit_permutation(unsigned int x)
{
	int t = x | (x - 1);
	return (t + 1) | (unsigned int)((~t & -~t) - 1) >> (bsf(x) + 1);
}

// bit permutation。nビット立っているものを列挙する
inline unsigned long long next_bit_permutation(unsigned long long x)
{
	long t = x | (x - 1);
	return (t + 1) | (unsigned long long)((~t & -~t) - 1) >> (bsf(x) + 1);
}

// x の p1からlen bitと p2 から len bit を入れ替える
template<class T>
T bit_swap(T x, size_t p1, size_t p2, size_t len)
{
	T mask = (static_cast<T>(1) << len) - 1;
	T ope = (x >> p1 ^ x >> p2) & mask; // 入れ替える場所のxorを求める
	return x ^ (ope << p1 | ope << p2); // 入れ替える場所をxor。
}

最新版は以下でメンテされるだろう。
ただし、あっちは、 #define long long long されているので注意が必要。
プロコン用テンプレート C++11

2014/07/06(Sun)プロコン用テンプレート C++11

はてブ数 2014/07/06 5:32 計算機な日記::プロコン つーさ

つーさが、ここ1ヶ月くらい前からAOJで遊びはじめて、
プログラミングコンテストとかで使ってるテンプレートです。
C++11です。

入出力が READ や read<..>(n次元); や readjag()で簡単に書けたり、
出力が、WRITE に vector を渡すと1行にスペース区切りで出してくれたりとか。

探索と幾何はそれなりにまとめた?
フローとかがなくてつらい。


続きを読む

2014/06/22(Sun)AtCoder Beginner Contest #11

はてブ数 2014/06/22 1:53 計算機な日記::プロコン つーさ

久々にAtCoderに出たよ!

http://abc011.contest.atcoder.jp/submissions/all?user_screen_name=ttsuki

D問題の大ジャンプが面白い問題だった。
ぎりぎり401点取れて42位、全完の中では下から2番目。。
順位表を眺めていて、この辺のレベルを面白いと思って解いているようじゃ、まだまだだなー。

最近個人的にプログラミングコンテストブームが再来して、AOJでICPC関連の問題解いて遊んでる。
人生において、プロコン問題が解けた瞬間が一番楽しいと思う。

2014/01/01(Wed)yamy(Yet Another 窓使いの憂鬱)でどこでもhjklカーソル移動

はてブ数 2014/01/01 16:18 計算機な日記::ボクと計算機 つーさ

あけましておめでとうございます。
本年も何卒よろしくお願いいたします。

日本で英語キーボードというとどうしても選択肢が限られてしまい、
最近のノートパソコンではキーボード配列を選べないことも多くなってきました。
キーボード配列ひとつで好きなノートPCが選べないのはもったいないですし、
かといってやはり記号を多く入力するプログラマにとって英語配列の魅力は捨てがたい。
結局、109日本語キーボードを104英語配列ドライバで動かすことに落ち着いているつーさです。

記号キーはキーボードに書いてある文字と違うものが出るので最初は戸惑いますが、
慣れてしまえばキーボードを見ることなんてないのでこれはこれで幸せです。

さて、タイトル。

文字を書いてるとき、ログを眺めてるとき、hjklでカーソル移動したいです。
前々から気になっていたyamyでのremapに挑戦。
http://knoike.seesaa.net/article/356046428.html

yamy は 窓使いの憂鬱の親戚で、
LLキーボードフックを使ってキーの入れ替えをしてくれるツールです。

続きを読む

2013/12/29(Sun)asusのタッチパッドでマウスの真ん中のボタンを有効にする

はてブ数 2013/12/29 5:14 計算機な日記::ボクと計算機 つーさ

touchpad で middle click ができないんだわ。設定画面も見つからない。

これでは、ブラウザ使っててもタブが閉じられないし、新しいタブで開けないし、
そのほか、ミドルボタンをフックして何かしてくれるようなツールも使えないジャマイカ。
前のS101使ってた時は、三本指タップができてたのに!

検索してもなかなか解決方法がわからなくて苦しんでたんだけど、やっと見つけた解決方法がこれ!
記事は zenbook 向けのものですが、私が最近買った taichi21 でもいけました。
http://wj32.org/wp/2012/12/19/asus-ux31e-setting-up-the-elantech-touchpad-driver-for-windows-8/

続きを読む

2013/12/28(Sat)Windows 8.1 の cygwin で group の permission が設定できない。

はてブ数 2013/12/28 6:25 計算機な日記::ボクと計算機 つーさ

概要
chmod してもグループに対するアクセス権がrwxのまま変更できない話。
Windows 8.1 に cygwin x64 を入れたら起こった。
/etc/passwd の 自ユーザのグループが513(なし)になってる。
のを544(Administrators)か545(Users)に直す。
すでにできてしまったファイルやディレクトリはchgrpで戻す。

内容。

新たにWin8ノートパソコンを買ったので環境構築の一環でcygwin x64を入れた。
無事インストールして、いざ使うかーと思って screen を起動しようとしたら

tu-sa@t21 ~
$ screen
Directory /tmp/uscreens/S-tu-sa must have mode 700.

ほう……。ならば?

tu-sa@t21 ~
$ ls -l /tmp/uscreens
合計 0
drwxrwx---+ 1 tu-sa なし 0 12月 28 05:21 S-tu-sa

tu-sa@t21 ~
$ chmod 700 -R /tmp/uscreens/S-tu-sa

tu-sa@t21 ~
$ ls -l /tmp/uscreens
合計 0
drwxrwx---+ 1 tu-sa なし 0 12月 28 05:21 S-tu-sa

はははこやつめ。

続きを読む

2013/12/28(Sat)Windows 8 PC に Windows 8.1 を入れるために必要なKB

はてブ数 2013/12/28 3:09 計算機な日記::ボクと計算機 つーさ

クリーンインストール/リカバリ直後とかで、Windows Updateしてなくて、
ストアにWindows 8.1へのアップグレードが出てこないPCを、
とりあえずWindows 8.1へアップグレードしたいときこのKBを入れる。
Windows Server 2012 R2への更新もこれでいける。
http://support.microsoft.com/kb/2871389
アップグレード後ちゃんとWindows Updateするべきなのは言うまでもない!

2013/11/16(Sat)問:加算の超最適化を実装せよ

はてブ数 2013/11/16 14:11 計算機な日記::プロコン つーさ

http://codegolf.stackexchange.com/questions/12664/implement-superoptimizer-for-addition

今Y個の0/1の2値のいずれかを取る変数x[0]...x[Y-1]がある。
こいつらの和がXになるかどうか を判定する論理式を作るプログラムを作る。
論理式には括弧 と and or not が利用できる。
論理式のスコアは、x[?]が評価された回数で定まる。

F(Y = 2, X = 1) := (x[0] & !x[1]) | (!x[0] & x[1]) ならば スコア は 4。

入力 Y,X に対して最もスコアが低くなるような論理式を生成して返すプログラムを書け。