1-4ビット目yyyyはxxの値によって変わりますが、フラグの値は$X$のMSBと$A$中の１の位置で決まります。$A$の１が$X$のMSBより左にあるとフラグは０、さもなければフラグは１です。よって$X$に対してこの引き算を全部試せば、MSBの数だけ１が立ったフラグが手に入ることになります。 これを利用して$X’$を作っているのが下の図です。$X$にフラグをつけて√w個コピーしたあと、フラグで区切られた各区間（ブロック）に対して上記の引き算を一度に実行し、その後yyyyの部分をビットマスクで0クリアしたのが$X'$となります。$X'$のビット長は$\sqrt{w}(\sqrt{w}+1)=w+\sqrt{w}$なので、２ワード上で演算すれば$X'$は定数時間で計算できるというわけです。 X'の１を定数時間で数える方法について １が立っているビットを定数時間で数えるのは結構難しいのですが、
http://herumi.in.coocan.jp/diary/1804.html#13 を解いた時の話。光成さんは実験的に解かれたようだったんですが、割と理詰めで解けたので、思考過程をダンプしてみます。元のコードは int calc(int a, int b, int s) { const int Q = 1 << s, Q2 = Q * 2, Q3 = Q * 3; assert(0 <= s && s <= 16 && && 0 <= b && b < a && a < Q * 4); int n = 0; for (;;) { if (a < Q2) { // A n = n * 2; } else if (b >= Q2) { // B n = n * 2 + 1; a -= Q2; b -= Q2; } else if (b >= Q && a < Q3) { // C a
はじめに はじめまして。 NTTデータ数理システムでリサーチャーをしている大槻 (通称、けんちょん) です。 C や C++ を使用しているとしばしばビット演算を行う場面が出て来ます。 計算機リソースが限られている状況では、ビットを用いることでデータ量を少なく済ませたり、計算コストを小さく抑えたりすることができるメリットがあります。 本記事では、ビット演算を用いて実現できる処理について、簡単なものから高度なものまで集大成します。極力わかりやすく頑張って執筆しました。特に前半 4 つはビットの説明の中でもかなりわかりやすい方だと思います。後半の 7 つのテーマは比較的高度なアルゴリズムの話題ですので、フラグ管理やマスクビットについて詳しく学びたい方は前半 4 つを中心に読んでいただいて、後半 6 つは必要に応じて読んでいただければと思います。反対にビットの知識はあってビットを用いたアルゴリズ
ビットごとの秘法と技法 から
最も右のビットの位置を知る法 TAOCP 7.1.3はbitwise tricks and techniques(ビットごとの秘法と技法)で楽しい話題が満載だ. このブログで以前取り上げたビットスワップもそこにある. 今回の話は計算機にある語xの最も右にある1のビットの位置を計算するもので, x = 0なら1のビットはないから, エラーか不定とするか無限大とするかだが, その辺はどうでもいいのでx≠0 の場合を考える. xに対してこの位置をρ(x)で表すので, 位置を求めるアルゴリズムをρ関数という. ρは右(right)のRに対応するギリシア語のアルファベット(小文字)である. これに対し最も左のビットはTAOCPではleftのLのギリシア語のλという. λはLisp屋にはちょっと困る命名だ. 二進法での計算に慣れている人は, 最も右の1のビットを取り出すのが簡単なことは知っている. x
ビットごとの秘法と技法 から
最も左のビットの位置を知る法 二進法で表したxの最も左の1のビットの位置λ(x)は, 2を底とする対数lgがあれば簡単だ. λ(x)=⌊lg (x)⌋ たしかに (lg 1) => 0 (lg 2) => 1. (lg 3) => 1.5849625007211563 (lg 4) => 2. (lg 5) => 2.321928094887362 (lg 6) => 2.584962500721156 (lg 7) => 2.807354922057604 (lg 8) => 3. になっている. TAOCPでの最初の方法は浮動小数点演算命令による. FLOTU y,ROUND_DOWN,x; SUB y,y,fone; SR lam,y,52 ここで fone=#3ff0000000000000. これでうまく行く理由だが, MMIXの浮動小数点はIEEE/ANSI standard
ビットごとの秘法と技法 から
この遷移を有向グラフにしたのが次の図である. それぞれのノードは入次数も出次数も2の正則グラフである. このグラフですべてのノードを経由して元へ戻るHamilton経路の一例が赤い矢印で, それが上にあったde Bruijnサイクルである. この例は 0000 の右に 1111 を置き, 0100 の後に反対の 1011 を置いた形になっている. 4ビットのde Bruijnサイクルがどのくらいあるか, 手元に計算機があるから全解探索をしてみた. その結果が下の図で16通りあった. 上の目の子で探した解は最下段の左から2つ目である. そのそれぞれに対するサイクルは次のようだ. 0000100110101111 0000100111101011 0000101001101111 0000101001111011 0000101100111101 0000101101001111 000010
注意: この記事は読んでも役に立ちません。頭を無駄に使いたい人向け。 普通のループは、たとえば 0 から 255 までなら、0 -> 1 -> 2 -> ... というようにループする。 そういう普通のループじゃなくて、ビットを逆転させた数字でループできたらいいのになぁということが最近あった。 0 -> 128 -> 64 -> ... のように。 探してみると、そういうページが見つかった。 さすがネットは広い。 コードは以下の通り。 int r = 0; // counter int s = 0; // bit-reversal of r/2< int N = 256; // N can be any power of 2 int N2 = N << 1; // N<<1 == N*2 do { printf("%u ", s); r += 2; s ^= N - (N / (r&-r)
Mega Man 2, like many games of its era, utilized a password system in order to continue your progress between game sessions. This removed the need for a battery in the game cartridge and allowed gamers to share passwords (and thus progress) with others. In Mega Man 2, the password is represented as a 5x5 grid in which the columns are labeled 1-5 and the rows A-E. Each password is composed of 9 cel
この記事はCompetitive Programming Advent Calendar Div2012、20日目の記事です。(余談：そういえば本日2012/12/20は良い日ですね！) はじめに 今回はDonald.E.Knuth著”The Art of Computer Programming”のVolume4-1の前半パートであるBitwise Tricks & Techniquesで取り上げられているビット演算について記事を書きたいと思います。ただし、ここで取り上げられているものは必ずしも競技プログラミングにおいて実用的とは限りません。すでに関数として定義されているものはそれを使った方が実装量が減らせてよいと思います。なので、「ビット演算やべぇおもしれぇ！！」と思ってもらう一助となることを目指した読み物、という感覚で読んでいただけると幸いです。 今回はC++言語を基本としてコードを
この記事はCompetitive Programming Advent Calendar Div2012の2日目の記事です。 12月20日追記： Darseinさんが20日目の記事で、ビット演算についての詳しい説明を紹介してくださっています！必読ですね！！！！：） はじめに Y＾´ ∨／／ ／,∠ ,. ' ／l／／／ ／, ' , '／ ! ｜ ｌ }´ 〈 〉 変 〈/ , ' ／／￣｀>< ／／／ ／／／ _,.=‐|'"´l ｌ〈 変 / 〈 態. ∨, '／l| ,.'-‐､｀/／｀7/ ／''"´__ ｜ ﾊ l丿 態 { 人） ! ! （／! |ヽ〈_ ・.ﾉ〃 〃 ／ '／⌒ヾ.! ,' !く ! ! （_ ト､__／ ヽ､_,.イ ／ｌ ｌ ｜:::::::｀｀`/:::::／...´..
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
