- 1 名前：デフォルトの名無しさん mailto:sage [2008/11/08(土) 20:32:00 ]
- 前スレ
【高速化】ビット演算 0x02
pc11.2ch.net/test/read.cgi/tech/1158367586/
過去スレ
0x01. pc8.2ch.net/test/read.cgi/tech/1123918075/
関連スレ
アセンブラ… (゜□゜) ↑アッー！↓
pc8.2ch.net/test/read.cgi/tech/1148402614/
関連情報
Hacker's Delight
ttp://www.hackersdelight.org/
ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか
ttp://www.amazon.co.jp/exec/obidos/ASIN/4434046683
ビットを数える・探すアルゴリズム
ttp://www.nminoru.jp/~nminoru/programming/bitcount.html
Bitboard
ttp://en.wikipedia.org/wiki/Bitboard
- 52 名前：デフォルトの名無しさん mailto:sage [2009/01/04(日) 09:42:34 ]
- ていうか、この方が短くなるんじゃないか？
if (h > '9') h -= 7;
return h & 0xF;
これを分岐無しにするともっと長くなりそうだが。
int n = (h > '9');
h += n;
n <<= 3;
h -= n;
return h & 0xF;
- 53 名前：デフォルトの名無しさん mailto:sage [2009/01/04(日) 12:41:25 ]
- 分岐は気になるけど確かに減るね・・・。
cpi, brvs, subi, andi, ret
の５命令でいけそうだ。
分岐なしの方は 1 ビットシフトしかないのでかなり長くなるはず。
- 54 名前：デフォルトの名無しさん mailto:sage [2009/01/04(日) 21:44:08 ]
- お世話になっております。
>>52
unsigned char ascii2hex(unsigned char h) {
h &= ~0x20;
if (h > '9') h -= 7;
return h & 0xF;
}
として、6ワードになりました。
8f 7d andi r24, 0xDF ; 223
8a 33 cpi r24, 0x3A ; 58
08 f0 brcs .+2
87 50 subi r24, 0x07 ; 7
8f 70 andi r24, 0x0F ; 15
08 95 ret
すばらしいです。
- 55 名前：デフォルトの名無しさん mailto:sage [2009/01/04(日) 22:50:41 ]
- h &= ~0x20; って必要？
- 56 名前：デフォルトの名無しさん mailto:sage [2009/01/04(日) 23:43:33 ]
- 要らないはず。
むかーし、Z80のプログラムを逆アセンブルしてたら
同じように16進ASCII2桁を数値に直すサブルーチンがあって
正確には覚えてないが
push af
a >>= 4
call half
pop af
half:
以下1桁分の計算
ret
のような感じの、半再帰的な造りに感動した覚えがある。
- 57 名前：デフォルトの名無しさん mailto:sage [2009/01/04(日) 23:46:02 ]
- ん、2桁がAに入るわけないな。
まあとにかく、サブルーチン内のわずか先を一度callするやり方、ってことで。
- 58 名前：デフォルトの名無しさん mailto:sage [2009/01/05(月) 00:56:37 ]
- 俺はそこで、半桁分変換するのに
DAAだかDADだかのBCD演算用の命令を使って、キャリーをうまく使って
分岐無しにしたような気がした。
どこか探せばあるかもね。
- 59 名前：デフォルトの名無しさん mailto:sage [2009/01/05(月) 19:16:06 ]
- h &= ~0x20はいらないですね。
5ワードの間違いでした。
>>56
試しに再帰で作ってみました。
unsigned char htoi(unsigned char h, unsigned char l);
2桁の16進文字を値にする関数をこのように宣言すると、
AVRの場合h はr24、 l はr22に入り、戻り値はr24になります。
Cから呼ばれる関数はr0,r18〜r27,r30,r31が破壊を気にせず使えます。
htoi: // 半再帰を使ってみる→ 11ワード
mov r23, r24 // tmp <= h
ldi r24, 0 // 戻り値を0へ初期化
rcall half // 相対コール(tmpの処理)
swap r24 // ニブルを交換
mov r23, r22 // tmp <= l
half: cpi r23, 0x3A ; 58
brcs .+2
subi r23, 0x07 ; 7
andi r23, 0x0F ; 15
or r24, r23 // 結果をr24へor
ret
- 60 名前：デフォルトの名無しさん mailto:sage [2009/01/05(月) 19:17:38 ]
- htoi: // 普通にhlを処理した場合→11ワード
cpi r24, 0x3A ; 58
brcs .+2
subi r24, 0x07 ; 7
cpi r22, 0x3A ; 58
brcs .+2
subi r22, 0x07 ; 7
andi r22, 0x0F ; 15
swap r24
andi r24, 0xF0 ; 240
or r24, r22
ret
ワード数的には変わりませんでした。
movとかldiが無駄のような、必要なような。
- 61 名前：デフォルトの名無しさん mailto:sage [2009/01/06(火) 01:24:17 ]
- 分岐無しのほうを頭捻って1命令 短くしたつもり
しかし分岐使うほうにまだ1命令負けてるのがなぁ
unsigned char d;
h = h + 0x41 & 0x9F;
d = (h >> 4) | (h << 4);
h = h - d & 0xF;
return h;
- 62 名前：デフォルトの名無しさん [2009/01/27(火) 21:18:44 ]
- あげ
- 63 名前：デフォルトの名無しさん [2009/02/21(土) 23:38:22 ]
- あげ
- 64 名前：デフォルトの名無しさん [2009/02/26(木) 16:00:28 ]
- 符号なし整数値について、1となっている
ビットのうちで、最下位のビット番号を
求める方法はありますか？
0x00000010 → 1
0x00100000 → 5
みたいな。
1のビット数は任意がいいですけど、
高速なら1ビット限定でもかまいません。
- 65 名前：デフォルトの名無しさん mailto:sage [2009/02/26(木) 16:22:20 ]
- シフトしながらカウントか、テーブル参照かな。
x に入ってるとすると、x ^ (x - 1) とか x & (x ^ (x - 1)) とか、
最下位の立ってるビット関係の値を取り出せる演算はあるけど、
ビット位置がうまく出てくる方法はないんじゃないかな。
- 66 名前：デフォルトの名無しさん mailto:sage [2009/02/26(木) 16:32:15 ]
- すべて、 テーブルにすればいいんじゃない？ で終わり。
- 67 名前：デフォルトの名無しさん mailto:sage [2009/02/26(木) 16:46:49 ]
- 最下位ビットを抜き出して、それから 1 を引いてビットを数える、とか
- 68 名前：デフォルトの名無しさん mailto:sage [2009/02/26(木) 17:25:41 ]
- ハッカーのたのしみp90
- 69 名前：デフォルトの名無しさん mailto:sage [2009/02/26(木) 20:58:20 ]
- これとかwww.nminoru.jp/~nminoru/programming/bitcount.html
あと、CPUによっては命令を持っていることもある。x86のbsfみたいに。
- 70 名前：デフォルトの名無しさん mailto:sage [2009/02/26(木) 21:45:26 ]
- 1bit限定なら、前スレにあったテーブル参照での逆算が使えるかもね
- 71 名前：デフォルトの名無しさん mailto:sage [2009/02/26(木) 21:47:50 ]
- >>70
まぁx&-xで最下位ビット抽出してからやればなんとかなるかも
int f(unsigned x){
x = x & -x;
//x = (x * 0x0722BED3) >> 27; // 64ビット乗算がないならこっち
x = (x * (0x0722BED3ULL<<5)) >> 32 & 31;
return "\0\1\13\2\10\14\34\3\11\32\15\17\35\27\4\21\37\12\7\33\31\16\26\20\36\6\30\25\5\24\23\22"[x];
}
- 72 名前：デフォルトの名無しさん mailto:sage [2009/02/26(木) 22:58:47 ]
- >>69は>>1にあるんだがなぁ…
- 73 名前：デフォルトの名無しさん mailto:sage [2009/02/27(金) 00:03:32 ]
- ＞＞71
なんでそんなのがわかるの？
天才ですか？
俺にはさっぱり・・・
returnで返しているのも何をしているのかわからん・・・
何かお勧めの本はありますか？
体育大学卒で組込みやってるあんぽんたんですが、
本を読む努力はします。
- 74 名前：デフォルトの名無しさん mailto:sage [2009/02/27(金) 00:33:06 ]
- return "\0\1\13\2\10\14\34\3\11\32\15\17\35\27\4\21\37\12\7\33\31\16\26\20\36\6\30\25\5\24\23\22"[x];
こう書くから判りにくいんだよ。
こう書き直したらどうだ?w
return x["\0\1\13\2\10\14\34\3\11\32\15\17\35\27\4\21\37\12\7\33\31\16\26\20\36\6\30\25\5\24\23\22"];
ギャグはさておき。
static const char table[] = {
0, 1, 11, 2, 8, 12, 28, 3,
9, 26, 13, 15, 29, 23, 4, 17,
31, 10, 7, 27, 25, 14, 22, 16,
30, 6, 24, 21, 5, 20, 19, 18
};
return table[x];
と同じだよ。
- 75 名前：デフォルトの名無しさん mailto:sage [2009/02/27(金) 00:33:45 ]
- "0123456789"[i%10]
みたいな書き方、
自分で積極的に使う必要は無いが
読めるようになっておく必要はあると思うぞ。
- 76 名前：デフォルトの名無しさん mailto:sage [2009/02/27(金) 07:28:19 ]
- (i%10)["0123456789"]
- 77 名前：デフォルトの名無しさん mailto:sage [2009/02/27(金) 07:32:13 ]
- >>74
同じじゃないだろ
char配列の終端に冗長な0が必要だ
- 78 名前：デフォルトの名無しさん mailto:sage [2009/02/27(金) 08:06:47 ]
- 同じだよ。
- 79 名前：デフォルトの名無しさん mailto:sage [2009/02/27(金) 10:14:24 ]
- >>73
組込み系か。
とりあえず「ハッカーのたのしみ」読んどけ。
あと、先輩や同業者が、計算機科学や情報系をバカにするかもしれないが、
話半分に聞いておくこと。
- 80 名前：デフォルトの名無しさん mailto:sage [2009/02/27(金) 12:27:36 ]
- >>73
文法周りはみんなが言ってくれたから計算回りだけ。
とりあえず前スレに分かりやすく書いてた人が居たから引用
前スレとの違いはp=5になった事ぐらい
ここから引用
周期2^p-1ビットの列があって、そこからpビットを切り出すと、オール0以外の全てのパターンが現れる
p=3の場合のM系列は例えばこう。
0011101
↓ (周期2^3-1=7で同じパターンの繰り返し)
001110100111010011101...
上の桁から3ビットを切り出すと、
001 (1)
_011 (3)
__111 (7)
___110 (6)
____101 (5)
_____010 (2)
______100 (4)
1〜7まで全部出るだろ。これに000だけ追加すればおｋ。
これだけだと順番がバラバラなので、テーブルと組み合わせる。
↓この文字列リテラルの部分な。
"xxxxxxx"[(ハッシュ計算式)]
すると、>>762-763になりますよ、と。ビット溢れによるマスクなども組み合わせているが。
- 81 名前：デフォルトの名無しさん mailto:sage [2009/02/28(土) 08:23:45 ]
- >>78
同じじゃない
実行時のメモリが1バイト冗長だ
- 82 名前：デフォルトの名無しさん mailto:sage [2009/02/28(土) 08:37:37 ]
- 大抵は4バイト違ってくるだろうな。
- 83 名前：デフォルトの名無しさん mailto:sage [2009/02/28(土) 08:42:16 ]
- ところが大抵はページサイズで区切られるので、
- 84 名前：デフォルトの名無しさん mailto:sage [2009/02/28(土) 09:03:18 ]
- 同じだよ。
- 85 名前：デフォルトの名無しさん mailto:sage [2009/02/28(土) 09:47:38 ]
- 似たような感じでNLZはできないものか？
- 86 名前：デフォルトの名無しさん mailto:sage [2009/02/28(土) 10:08:47 ]
- NLZって？
- 87 名前：デフォルトの名無しさん mailto:sage [2009/02/28(土) 10:13:31 ]
- ニュージーランド
- 88 名前：デフォルトの名無しさん mailto:sage [2009/02/28(土) 13:51:09 ]
- Number of Leading Zero だろう。頭からゼロが何個続いてるか数える。
シフトしてって数えるとか、浮動小数点フォーマット変換でとかあるけどあまりスマートな方法がないよね。
- 89 名前：デフォルトの名無しさん mailto:sage [2009/02/28(土) 14:14:26 ]
- ないからわざわざそういう命令があったりするんだろうね。POWERとかだっけ？
DSPとかだとビット並びを反転させる命令があるから、それと組み合わせるか。
- 90 名前：デフォルトの名無しさん mailto:sage [2009/02/28(土) 16:03:40 ]
- DSPだと、小数正規化用の命令が使える
- 91 名前：デフォルトの名無しさん mailto:sage [2009/02/28(土) 16:42:35 ]
- 体育会系で組込みはまだいるかもしれないが、
体育大学で組込みは希少だよな。日本全国探してもレア？
- 92 名前：64 mailto:sage [2009/03/01(日) 21:54:40 ]
- レスくれたひと、どーも。
簡単に言うと>>67なんですね。
ビットカウントのアレは知ってたんですが、
応用ができませんでした。
- 93 名前：デフォルトの名無しさん [2009/03/08(日) 10:14:52 ]
- あげ
- 94 名前：デフォルトの名無しさん mailto:sage [2009/03/13(金) 05:58:26 ]
- 1つかまたは0個のビットが立っている時に何番目のビットが立っているか。(上からでも下からでも、より速い方)
お願いします。
- 95 名前：デフォルトの名無しさん mailto:sage [2009/03/13(金) 06:05:16 ]
- すぐ上にありました。すみません。
- 96 名前：デフォルトの名無しさん [2009/03/20(金) 21:41:48 ]
- 2進数や16進数の為の代数学とか無いのかな？
例えば32bit符号付き整数の絶対値を求める式を、定理を使って単純に変形するだけで、
andとかshiftとかmulみたいな単純な操作のみで構成された式に変形できる公理系とかそういうの
x < 0 ? -x : x
={なんか、分岐の融合法則とかそういうの}
(n ^ (n >> 31)) - (n >> 31)
こういう等式変換の形でアルゴリズムを計算でできれば、
勘だけではできないときに色々と役立つんじゃないかなーと思うだけど
つーか絶対ある筈なんだけど、俺はそういう噂すら知らないんで
- 97 名前：デフォルトの名無しさん mailto:sage [2009/03/20(金) 22:39:46 ]
- 合同式のことかと思ったが、もっと低レベルな話みたいだ。
ビット演算で絶対値を求めたいなら、２の補数を調べるといい。
2進数とか16進数を難しいと思ってるかもしれないが、他の人は誰も
そう思ってないから。
- 98 名前：96 mailto:sage [2009/03/21(土) 00:45:51 ]
- n < 0 ? -n : n
={ 2の補数 : -n = ~n + 1 }
n < 0 ? ~n+1 : n
={ n+0 = n }
n < 0 ? ~n+1 : n+0
={ --x = x, - 0 = 0 }
n < 0 ? ~n-(-1) : n - 0
={ n < 0 ? -1 : 0 <=> (n>>31) …(*}
(n < 0 ? ~n : n) - (n >>31)
={ ~n = n^(-1), n^0 = n}
(n < 0 ? n^(-1) : n^0) - (n >>31)
={ (*) }
(n^(n>>31)) - (n>>31)
? : 演算子の単調性とか一部証明無しで決め打ちしてますができました
4番目の変形以降は知ってないとできませんね、恐らく常識なんでしょうけど
>>96はその常識をまとめてあったり、こういう演算の性質について
群とかそういった代数学の概念での議論とかが載ってる文献などありませんかという意味でした
- 99 名前：デフォルトの名無しさん mailto:sage [2009/03/25(水) 04:25:32 ]
- 右シフトが論理シフトだったら
(n^-(n>>31))+(n>>31)
かな？
nが1の補数だったらどうなるんだろう
- 100 名前：デフォルトの名無しさん mailto:sage [2009/03/25(水) 04:27:42 ]
- nが1の補数だったら
n<0?~n:n
→n<0?n^-1:n^0
→n^(n>>31)
かな。
- 101 名前：デフォルトの名無しさん mailto:sage [2009/03/25(水) 04:38:12 ]
- 一般変形としてはこんな感じか。
x<y?z:w
→x-y<0?z:w
→z&(x-y>>31)|w&(~(x-y>>31))
x<=y?z:w
→y<x?w:z
x>y?z:w
→y<x?z:w
x>=y?z:w
→x<y?w:z
x=y?z:w
→x-y=0?z:w
→x-y<0&y-x<0?w:z
→w&((x-y>>31)&(y-x>>31))|z&(~((x-y>>31)&(y-x>>31)))
- 102 名前：デフォルトの名無しさん mailto:sage [2009/03/25(水) 04:39:43 ]
- x<0?y:y+z
→y+(z&(x>>31))
- 103 名前：デフォルトの名無しさん mailto:sage [2009/03/25(水) 05:50:18 ]
- 条件式使うならビットシフトまで落とす意味ない。
- 104 名前：デフォルトの名無しさん mailto:sage [2009/03/26(木) 18:53:33 ]
- 3項演算子を使うとx86だと式の計算以外に少なくとも3〜4クロック余計にかかるから、
他で4クロック以上重くなるというのでなければビットシフトまで落とす意味は十分にある。
- 105 名前：デフォルトの名無しさん mailto:sage [2009/03/26(木) 19:34:12 ]
- ジャンプはvだということを考慮すると2〜4クロックだぞ。
- 106 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/03/26(木) 19:37:54 ]
- CMOVって重たかったっけ？
y + ((x < 0)? 0 : z)に変形すれば
mov eax, dword ptr [y]
mov edx, dword ptr [x]
xor ecx, ecx
cmp eax, 0
cmovae ecx, dword ptr [z]
add eax, ecx
- 107 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/03/26(木) 19:45:46 ]
- もしくはこうかｗ
y + srl(x, 31) * z
- 108 名前：デフォルトの名無しさん mailto:sage [2009/03/26(木) 20:08:02 ]
- いや、それは逆に遅くならないか？
cmov系はフラグが確定するまで待機するから。
- 109 名前：108 mailto:sage [2009/03/26(木) 20:08:44 ]
- >>107
それはないｗ
- 110 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/03/26(木) 20:17:24 ]
- じゃあこれで
movd xmm0, dword ptr [y]
movd xmm1, dword ptr [x]
pxor xmm2, xmm2
movd xmm4, dword ptr [z]
pcmpgtd xmm2, xmm0
pand xmm2, xmm3
paddd xmm0, xmm2
movd eax, xmm0
どうみてもネタです。本当にありがとうございました。
- 111 名前：デフォルトの名無しさん [2009/04/18(土) 06:06:04 ]
- a
- 112 名前：デフォルトの名無しさん [2009/04/28(火) 19:50:17 ]
- ほしゅ
- 113 名前：ほしゅ [2009/05/15(金) 16:34:50 ]
- >>58 daa を使ったのは、 add a,0x90; daa; adc a,0x40; daa といった感じ。 dasを使ったのは cmp a,10; sbc a,0x69; das といった感じ。 das方式の 参考ページは www.df.lth.se/~john_e/gems/gem003a.html
- 114 名前：,,・´∀｀・,,）っ-○○○ mailto:sage [2009/05/15(金) 20:53:01 ]
- BCD演算ってそもそも遅くね？
- 115 名前：デフォルトの名無しさん mailto:sage [2009/05/15(金) 22:00:47 ]
- あんまり変わらなかった
- 116 名前：デフォルトの名無しさん mailto:sage [2009/05/17(日) 23:45:35 ]
- これさ、○○与えると△△返すビット演算教えてください、みたいな感じで
それに人間が答えてるけどさ、
一般的に反復深化の自動計算でビット演算はじき出すフリーソフトとかないんだっけ？
- 117 名前：デフォルトの名無しさん mailto:sage [2009/05/17(日) 23:49:36 ]
- 反復深化？
- 118 名前：,,・´∀｀・,,）っ-○○○ mailto:sage [2009/05/18(月) 00:15:38 ]
- サブネットマスクでも計算するの？
てかその手のは社内ツールであったな。
- 119 名前：,,・´∀｀・,,）っ-○○○ mailto:sage [2009/05/18(月) 00:17:55 ]
- tmkk氏がBerkeleyのSISってツールがあるって言ってたな
- 120 名前：デフォルトの名無しさん mailto:sage [2009/05/19(火) 02:55:16 ]
- 記憶が正しければ、今はBCD系はMMX系統の余った回路使って演算してる筈。
- 121 名前：,,・´∀｀・,,）っ-○○○ mailto:sage [2009/05/19(火) 03:53:50 ]
- ないない。
BCDって64ビットで無効命令だぜ？
Core 2あたりで除算回路そのものが高速化されてるあたり、IDIVと同じようなことやってんだろ
- 122 名前：デフォルトの名無しさん [2009/05/24(日) 21:17:29 ]
- あ
- 123 名前：デフォルトの名無しさん mailto:sage [2009/05/29(金) 06:15:50 ]
- //INVERSEはビットの左右を反転する処理
c = INVERSE(a);
d = INVERSE(b);
e = c + d;
f = INVERSE(e);
このようにaとbからfを求める処理があるとき
INVERSEを無くしたり減らしたりはできるでしょうか
- 124 名前：,,・´∀｀・,,）っ-○○○ mailto:sage [2009/05/29(金) 07:25:25 ]
- キャリーの逆ができる回路があるならな。
大ヒント
a + b
= (a & b) + ((a ^ b) << 1)
- 125 名前：デフォルトの名無しさん mailto:sage [2009/05/31(日) 10:10:12 ]
- unsigned reverse_add(unsigned x, unsigned y) {
do {
unsigned c=x&y;
x^=y; y=c>>1;
} while(c!=0);
return x;
}
- 126 名前：,,・´∀｀・,,）っ-○○○ mailto:sage [2009/05/31(日) 10:47:55 ]
- ARMとかならアンロールしてプレディケートすれば上手い具合に分岐除去できるな
- 127 名前：デフォルトの名無しさん mailto:sage [2009/06/06(土) 18:55:12 ]
- >>124
a+b = (a^b) + ((a&b)<<1)
の間違い？
- 128 名前：,,・´∀｀・,,）っ-○○○ mailto:sage [2009/06/12(金) 01:37:04 ]
- >>127
そーでしたorz
- 129 名前：デフォルトの名無しさん mailto:sage [2009/06/20(土) 16:18:05 ]
- 952 名前：デフォルトの名無しさん 投稿日：2009/06/13(土) 22:16
C言語をはじめたばかりであまりわからないのですが、
ビットシフトはなんの役に立つのでしょうか？
953 名前：デフォルトの名無しさん 投稿日：2009/06/13(土) 22:32
>>952
例えば、32bit符号無し整数の変数があり、
先頭から8bitごとにARGBを表しているとする。
(32bit画像の1画素)
すると例えば、値を使用する前に2つを分離しなければならないから、
以下のようにする。
a = (x >> 24);
r = 0xFF & (x >> 16);
g = 0xFF & (x >> 8);
b = 0xFF & x;
- 130 名前： ◆0uxK91AxII mailto:sage [2009/06/20(土) 17:41:04 ]
- >>129
a = *((unsigned char *)&c+3);
以下略。
- 131 名前：デフォルトの名無しさん mailto:sage [2009/06/21(日) 00:01:18 ]
- エンディアン依存のコードはお行儀悪いんじゃなかった？
- 132 名前： ◆0uxK91AxII mailto:sage [2009/06/21(日) 08:04:17 ]
- ぐはぁ。
- 133 名前：デフォルトの名無しさん mailto:sage [2009/06/30(火) 01:49:31 ]
- >>123
本質的に難しいね
通常の加算の出力の MSB が入力の全ビットに依存するところを
加算命令が全部１命令でやってるわけで、
その左右反転の LSB が入力の全ビットに依存するような演算はバラすと結構かかる。
反転と再反転やりながら同時に加算もする方法を考えてみたけど
結局加算をバラすしかなくてだめだった。
(c & 0xAAAAAAAA)+(d & 0xAAAAAAAA) とかいろいろ考えたんだが。
逆演算の減算命令使うかなあと思ったけど、それも結局
「MSB が他のすべてのビットに影響を与える力」しかないし、
LSB に対する計算力が全くない。
結局やってることも補数の足し算だしね。
残るは特定係数の乗算？
それでもやっぱり基本的に LSB が上位ビットに無視されちゃう構造だし…。
なんか出力の LSB が入力の複数の上位ビットに依存するような便利な命令ないっすか？
右シフトくらいしか思いつかない…
- 134 名前：133 mailto:sage [2009/06/30(火) 03:39:26 ]
- >>123 左右反転加算
３による除算命令を使って何かできないか？
b = a/3 の演算は次のような演算とみてよい。
c = a[MSB]; //逆キャリー
for(i=MSB-1;i<LSB;i--){ // 以下はいわゆる「筆算」による除算
b[i] = (c<<1 & a[i]) >= 3;
c = (c<<1 & a[i]) % 3;
}
一方加算 b = a0 + a1 は次の通り。
c = 0;
for(i=LSB;i<MSB;i++){
b[i] = a0[i]^a1[i]^c;
c = a0[i]&a1[i] | a0[i]&c | a1[i]&c;
}
結構構造が似てる気がするのだが。
それでいて a/3 は LSB へ向かって結果が伝搬し、下位からの影響はない。
a/3 が１入力演算なので２入力演算な左右反転加算にはまだ遠いが…
なにか道が開けるかもしれない。
- 135 名前：133 mailto:sage [2009/06/30(火) 03:42:52 ]
- >>134
訂正
b[i] = (c<<1 & a[i]) >= 3;
↓
b[i] = (c<<1 | a[i]) >= 3;
- 136 名前：デフォルトの名無しさん [2009/07/01(水) 13:27:12 ]
- >>123
難しい
無理な気がする
- 137 名前：デフォルトの名無しさん mailto:sage [2009/07/01(水) 20:33:21 ]
- おいおい、どうして>>125を無視する
inverseせずに出来てるじゃないか
- 138 名前：デフォルトの名無しさん mailto:sage [2009/07/01(水) 20:50:37 ]
- ああ、ごめん
無視してないよ
コードも実行してみたよ
>>125よりいいのを考えてて思いつかなかった
- 139 名前：デフォルトの名無しさん mailto:sage [2009/07/02(木) 02:33:25 ]
- >>125 は面白くていいんだけど
ちょっと最悪計算量が大きくない？
0x00000001 = reverse_add(0x80000000, 0xFFFFFFFE) とか。
64ビットとかだったら64回くらいループしそうだし。
- 140 名前：デフォルトの名無しさん [2009/07/05(日) 21:53:38 ]
- >>116
そんなソフトあるんか・・・ 世界は広いな
- 141 名前：デフォルトの名無しさん mailto:sage [2009/07/06(月) 18:55:03 ]
- 60で割った余りが0かどうか調べるにはどうすればいい？
- 142 名前：デフォルトの名無しさん mailto:sage [2009/07/06(月) 19:20:07 ]
- 60で引いていって60以下になったらそれが答えです
- 143 名前：デフォルトの名無しさん mailto:sage [2009/07/06(月) 19:54:13 ]
- 以下じゃなくて未満ですた
- 144 名前：デフォルトの名無しさん mailto:sage [2009/07/06(月) 20:01:13 ]
- if(0 == (n + 4) >> 6)
{
}
- 145 名前：デフォルトの名無しさん mailto:sage [2009/07/06(月) 20:58:51 ]
- >>144
nを60にしても1なんですけどー
- 146 名前：デフォルトの名無しさん mailto:sage [2009/07/07(火) 03:43:18 ]
- >>141 if( (n%60) ) { ０じゃないほう } else { ０のほう }
％は言語によって MOD とかもある。
- 147 名前：デフォルトの名無しさん mailto:sage [2009/07/07(火) 04:08:05 ]
- え、マジで言ってる？
このスレの住人にも不可能なの？
- 148 名前：,,・´∀｀・,,）っ-○○○ mailto:sage [2009/07/07(火) 20:47:14 ]
- 分岐のオーバーヘッドは高くないと仮定して、除算の平均回数を減らすほうがいいだろ
if ((n & 3) || (n % 60))
- 149 名前：デフォルトの名無しさん mailto:sage [2009/07/08(水) 00:49:59 ]
- 0 4 8 12 16 20 24 28 32 36 40 44 48 52 56
の時だけ割り算か。1/4になったね。
4の倍数に注目したらもうちょっとなんとかならない？
- 150 名前：デフォルトの名無しさん mailto:sage [2009/07/08(水) 00:52:29 ]
- >>148
if(n & 3) return 0;
x=((n>>2)*0x01111111)>>12;
return !x || x==0xf;
まあ掛け算で桁あふれのない n<16444 どまりだけどね。
- 151 名前：150 mailto:sage [2009/07/08(水) 01:14:43 ]
- x=(((n>>2)*0x01111111)>>12 & 0xf);
& 0xf を忘れてた
- 152 名前：デフォルトの名無しさん mailto:sage [2009/07/08(水) 02:54:49 ]
- すげー乗算になってさっぱり判らん
|
 |
