【高速化】ビット演算　0x02

前スレ
ビット演算
http://pc8.2ch.net/test/read.cgi/tech/1123918075/


関連スレ
アセンブラ…　(゜□゜) ↑アッー！↓
http://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

　　　　/ノ 0ヽ
　 　＿|＿＿_|＿　　下がってろウジ虫共！
　 　 ヽ|・∀・|ﾉ　　　　　訓練教官のようかんマン先任軍曹が2getだ！
　　　　|＿＿|
　　　　　|　|

>>1　貴様！俺のかんてんをどうするつもりだ！
>>3　あんこを入れる前と後に「サー」と言え！
>>4　ふざけるな！茶をだせ！茶っ葉落としたか！
>>5　貴様にはふやけたもなかをかき集めた値打ちしかない！
>>6　異人の手先の駄カステラめ！
>>7　まるでそびえ立つ葛だ！
>>8　栗を切り取って貴様の価値を絶ってやる！
>>9　お茶請けにもなれないゼリー風情が気取った事を言うな！
>>10-999　虎だ！虎になれ！虎屋のようかんを思い出せ！
>>1000　気に入った！家に来て俺を食っていいぞ！

　　　　∧
　　　 < | >　　　　　俺はグラットン持ちの通りすがりのナイトであって
　　　　|.|.|　　　　　　　　　　　　　　3getしたがどうやってブロントって証拠だよ！！
　　　　|.|.|
　　　　|.|.|
　　　 < | > 　　　　　おいィ？お前それで良>>1のか？　
　　　...| | |.　　　　　 仏の顔を>>2度までという名セリフを知らないのかよ
　　　...| | |. 　　　　　暗黒が持つと逆に頭がおかしくなって>>4ぬ
　　　...| | |.　　　　　 グラットンす>>5いですね
　 　 .< .| .>　　　　　>>6駄にaguるなネットポリスに捕まりたいのか？
　/(.._..|..|..|.._..)ヽ　　 それほどでも>>7い
　>.─＜＞─.<　　　このままでは俺の寿命がストレスでﾏｯ>>8なんだが・・
　ヾ￣ヾ .√ ")'　　　>>9枚で良い
　　　　.| .|　　　　　　俺の怒りが有頂>>10になった
　　　　.| .|
　　　　.| .|　　　　　　おれパンチングマシンで>>100とか普通に出すし
　 　 　 ) (
　　　　.▽

廃人向けビット演算の知識を扱うスレはここですか？

団子(◆DanGorION6)はWEBページからデータを自動収集して会話する人工無能なので
必要なコピペを引き出したらあとは放置しましょう。
待機モード中の自動応答に本気でレスすると、無駄にログが流れ読みにくくなりますし
他の利用者の妨げになります。

>>1
乙です

Java使っててもたまにお世話になるから侮れん。

　＊　 　　　+　　　　巛 ヽ
　　　　　　　　　　　　〒　!　　　+　　　　。　　　　　+　　　　。　　　　　＊　 　　　。
　 　　　　+　　　　。　 | 　|
　　　＊　 　　　+　　 /　/　　　イヤッッホォォォオオォオウ！
　　　　　　 ∧＿∧ /　/
　　　　　　（´∀｀　/　/　+　　　　。　　　　　+　　　　。　　　＊　 　　　。
　　　　　　,-　　　　　ｆ
　　　　　 / ュヘ　　　　| ＊　 　　　+　　　　。　　　　　+　　　。　+
　　　　　〈＿｝ ）　　　|
　　　　　　　 /　　　　! +　　　　。　　　　　+　　　　+　　　　　＊
　　　　　　 ./　　,ヘ　 |　　　　　　このスレッドは１０００を超えました。
　ガタン　||| j　　/　|　 | |||　　　　　　　　次スレも…BITクオリティ！！
――――――――――――　　　　　　 　 http://pc8.2ch.net/tech/

って1000取ろうとしたらすっかり忘れてた。

何はしゃいでるんだか。
こういう奴死んでくれないかな。

age

age

>>8
取れてるじゃん。

オセロで空白位置 m に打ったときに返るパターンを取得するプログラムで
分岐を使わないのができた

uint64 wh = white & 0x7e7e7e7e7e7e7e7e; // 横移動のための番人
uint64 rev = 0;
uint64 e1, e2, e3, e4, e5, e6; // 空白から続く白石列
uint64 b1, b2, b3, b4, b5, b6; // 黒石から続く白石列
e1 = (mask0 <<1) & wh;
e2 = (e1 << 1) & wh;
e3 = (e2 << 1) & wh;
e4 = (e3 << 1) & wh;
e5 = (e4 << 1) & wh;
e6 = (e5 << 1) & wh;
b1 = (black >> 1) & wh;
b2 = (b1 >> 1) & wh;
b3 = (b2 >> 1) & wh;
b4 = (b3 >> 1) & wh;
b5 = (b4 >> 1) & wh;
b6 = (b5 >> 1) & wh;
rev |=
e1 & b1 |
e1 & b2 | e2 & b1 |
e1 & b3 | e2 & b2 | e3 & b1 |
e1 & b4 | e2 & b3 | e3 & b2 | e4 & b1 |
e1 & b5 | e2 & b4 | e3 & b3 | e4 & b2 | e5 & b1 |
e1 & b6 | e2 & b5 | e3 & b4 | e4 & b3 | e5 & b2 | e6 & b1;

↑は 右方向だけのコード。他の7方向についても同様

だけど、条件分岐を使って書いたコードよりかなり遅い
もっと高速化できないものか

分岐を排除すれば早くなるなんてのは200段くらいのキチガイパイプライン
でもない限りありえない。
2項選択くらいならconditional move使えば簡単に表現できる。

x86ならレジスタ数が少ない上に32ビットレジスタ2本でようやく1つの64ビット値だから
それだとロード・ストアが頻発して全然速くない。
へたに1マス1ビットに割り振るよりは1バイトに振ったほうが小回りが利く分速くなることもある。

最後の部分は
rev |=e1 & (b1 | b2 | b3 | b4 | b5 | b6) |
e2 & (b1 | b2 | b3 | b4 | b5) |
e3 & (b1 | b2 | b3 | b4) |
e4 & (b1 | b2 | b3) |
e5 & (b1 | b2) |
e6 & b1;
とすれば、論理演算の回数を ４２ から 26回に減る
さらに or の部分をまとめれば
rev |= e6 & b1;
rev |= e5 & (b1 |= b2);
rev |= e4 & (b1 |= b3);
rev |= e3 & (b1 |= b4);
rev |= e2 & (b1 |= b5);
rev |= e1 & (b1 | b6);
論理演算の回数は 17回

WORD単位の方が速いことも多いような。

そういうの考慮したベンチマークとかシミュレーションとか
AMD が出してたのがあるような気がするけどなんだっけ…

x86の演算は基本的に２オペランドベースで破壊的。
つまり
　　src1 = func(src1, src2)

src1の値を保存したい場合は待避が必要になる。
レジスタ間移動

失礼

レジスタ間移動だけでも整数の論理算術演算と同様にクロック数と
演算ユニットを使うし、ロード・ストアが絡むとさらに遅延が大きくなる。

x86でこの手の最適化をやる場合、テンポラリ変数をなるべく多用しない
（３２ビットで同時に３～４くらいに抑えるべき）のと、全部 &= や |= で
書いてみれば、吐き出される命令数が最低どのくらいになるかは
見当がつくと思う。

下記のように書き換えれば、使用変数が減る
uint64 wd = white & 0x007e7e7e7e7e7e00;//斜め移動のための番人
uint64 rev = 0;
uint64 e1, e2, e3, e4, e5, e6;//空白から続く白石列
uint64 b1;//黒石から続く白石列
e1 = (m << 9) & wd;
e2 = (e1 << 9) & wd;
e3 = (e2 << 9) & wd;
e4 = (e3 << 9) & wd;
e5 = (e4 << 9) & wd;
e6 = (e5 << 9) & wd;
rev |= e6 & (b1 = (black >> 9) & wd);
rev |= e5 & (b1 |= (b1 >> 9) & wd);
rev |= e4 & (b1 |= (b1 >> 9) & wd);
rev |= e3 & (b1 |= (b1 >> 9) & wd);
rev |= e2 & (b1 |= (b1 >> 9) & wd);
rev |= e1 & (b1 | (b1 >> 9) & wd);

e1～e6 は高々1ビットだけがセットされているので、
e6 = (m << 6*6) & wd;
とし、
rev |= e6 & (b1 = (black >> 9) & wd);
rev |= (e6>>=6) & (b1 |= (b1 >> 9) & wd);
としてもよさそうだが、一度にシフトすると番人を飛び越してしまうのでよろしくない

結局は子供の遊びだな

子供が遊びでこんなことをするとは恐ろしい時代になったんだな。

子供の遊びを大人がやっているだけだろ。

大人の遊びを子供がやる時代だから。

つかお前らも子供の頃MSXBASICからマシン語打ち込んだり
ニーモニック丸暗記して作ったプログラムに独自のチェックサムﾓﾄﾞｷつけたりして
紙に書いてセーブしてﾜｸﾜｸしてただろ。

大人はそんな無駄でアホな事まずやらねぇ

ビットボードによるオセロの話

A1, B1, ... H1 などの横一列の状態を一意の数字（インデックス）に変換し、
あらかじめ作成しておいたテーブルを引きたい
マスの状態は白黒空の3種類なので、空:0,黒：1,白２として 3倍しながら値を足していけば
インデックスを計算できる。

#define isB(p) ((black&p)!=0)
#define isW(p) ((white&p)!=0)
#define V(p) (isB(p) ? 1 : isW(p) ? 2 : 0)
#define INDEX8(p1, p2, p3, p4, p5, p6, p7, p8)\
(((((((V(p1)*3+V(p2))*3+V(p3))*3+V(p4))*3+V(p5))*3+V(p6))*3+V(p7))*3+V(p8))

INDEX8(A1, B1, C1, D1, E1, F1, G1, H1);

この処理をビット演算を使って、華麗に高速に行う方法はないのでしょうか？

1マスが2ビット（黒：01, 白：10, 空：00）で、8マス分の情報が下位16ビットに並んでいれば
分割統治法が使えそうだ

t = x & 0xcccc; x = (x & 0x3333) + (t >>= 1); x += t >>2;
t = x & 0xf0f0; x = (x & 0x0f0f) + (t >>= 3); x += t >> 4;
t = x & 0xff00; x = (x & 0x00ff) + (t >>= 7); x += t >> 8;

論理演算 6回、シフト 6回、加算 6回

3倍して足していく方法は、乗算 7回、加算7回 なので、少し速そう

t = x & 0xcccccccc; x = (x & 0x33333333) + (t >>= 1); x += t >> 2;
t = x & 0xf0f0f0f0; x = (x & 0x0f0f0f0f) + (t >>= 3); x += t >> 4;
t = x & 0xff00ff00; x = (x & 0x00ff00ff) + (t >>= 7); x += t >> 8;
ix1 = x >> 16;
ix2 = x & 0xffff;

とすれば、2行分のインデックスを同時にもとめることができる。
64ビット変数を使えば4行分をまとめて計算できる。
それならかなり高速になりそう

しかし、ビットボードは白黒別々なので、それを2ビットごとにまとめなくてはいけない
その処理に時間がかかりそうだ

2ビットごとにまとめる処理は、いわゆるシャフルだ
下位32ビットについて、

b = black & 0xffffffff;
b = ((b & 0xffff0000) << 16) | (b & 0xffff);
b = ((b & 0xff00ff00ff00) << 8) | (b & 0xff00ff00ff);
b = ((b << 4) | b) & 0x0f0f0f0f0f0f0f0f;
b = ((b << 2) | b) & 0x3333333333333333;
b = ((b << 1) | b) & 0x5555555555555555;

で間に０を入れ、白も同様に処理し、

x = b | (w << 1);

とすれば、2ビットごとにまとめることができる。
あとは >>30 の処理を行えば、下4行分のインデックスが求まる。

>>29
間違ってない？

ビット演算だけで四則演算ってできるの？

それはギャグで言ってるのか

加算器って基本はビット演算だそ。

回路図や真理値表は以下のページにあるぞ。
http://ja.wikipedia.org/wiki/%E5%8A%A0%E7%AE%97%E5%99%A8

いわゆるCPUだとかマイクロ・プロセッサつーのは、
その奥深くに 加算器に演算レジスタがあって、
ノイマン型にプログラム通りに計算をするためのものなんだから。

減算 や 負の数を扱うには「2の補数」
http://ja.wikipedia.org/wiki/2%E3%81%AE%E8%A3%9C%E6%95%B0
と言った捉え方で数を扱うのだ。

ビット演算だけで発明ってできるの？

ビット演算があれば、何でもできる。

ビット演算ができれば、僕にも彼女ができたりしますか？

当たり前。

or and not があれば全ての演算ができる？

NANDがあれば、何でもできる。

NORでもいいぞ

わかってないな

元気ががあれば、何でもできる。

行けば分かるさ

やっぱ、NANDとNORのハイブリットが良い？

Trががあれば、何でもできる。

Magic Algorithm
http://aggregate.org/MAGIC/

>>48
ひょっとしてradiumあたりで見た輩か？
>>1のサイトでとりあげられてる。
せめて>>1のサイトくらいみればよいのに・・・

C++やJavaだとどちらかというと保守性重視だから
性能改善要求出る前にビット演算使うと白い目で見られる。

>>50
例え処理が１行だけであっても、関数（インラインで良い）にしとけば文句でないはず。

>>51
勿論明瞭なコメント付きでな。

>>51
ついでに代替コードを書いておくとなお良い。

ゴリゴリのチューニングが求めらるような場面でもなければ、たいていはコンパイラの最適化だけで事足りるわけだが。

スクリプトでマスかいてろ

>>54
確かにそれで文句が出ないどころかメンテしやすければ褒められるべきところではあるが
多少の遊び心があってもそれはそれで許される。
>>51-53のようなことをしてあれば。
（代替コードのテストも必要なことは当然なので、プログラマの負担はアップするが）

ビット演算による最適化が必要で
パフォーマンス的に代替が効かないからこそ
そういうコードを書くわけだから
同等以上の速度が出た上に読みやすいコードを出せなければ
批難する事はできない。

もちろん意味もなくビット演算するアホの話は別として。

でも普通インラインアセンブラ使うよね。そういうビット演算だと。
上で出てるようなCでなんて書かないよ。

いや、俺はループアンローリングだとかプロセッサのスケジューリング管理
なんか考えたくないからC言語で書くけどね。
まぁ、どうしてもビット回転(rotate)が必要ならインラインアセンブラの
使用も検討するが。

インラインアセンブラはアセンブラとは違うよ

>>60
いや、当たり前の事実を主張されてもなぁ。
しかもなぜにこのタイミングで？わけわからん。

>>60
何が違うの？

ものほんのアセンブラならそもそも命令セットの数が違うみたいな？

なんつー理屈だ。

寧ろインラインアセンブラだとCコード部とのI/Fが簡単に書けるメリットはあるね。

ネイティブアセンブラ
　C言語との連携は関数呼び出しの形でのみによって実現される。
　殆どのメモリアクセスはシンボルではなくオフセット値での指定となるからめんどい。
　最適化の善し悪しはすべて自分の腕にかかっている。

インラインアセンブラ
　Cのソースに埋め込むことが出来るので、必要な箇所を個別に関数化する必要がない。
　関数内の局所変数にシンボリックにアクセスできる。
　一部のコンパイラはインラインアセンブラで書いた箇所も勝手に最適化してくれやがる。

スレ違いだ。他所でやれ。

論理演算部分をインラインアセンブラ化するのに、
どうして「プロセッサのスケジューリング管理」なんて話が出てくるのか誰か教えて！

「プロセッサのスケジューリング管理」の意味はわかっているか？

大方タイムスライスと勘違いしているんだろうけど。

>>67
パイプラインでな、処理を円滑に進めるためには、命令の実行順序を適切に
並び替える必要があるんだ。命令実行順序の決定をスケジューリングという。
命令実行スケジューリングはふつうコンパイラが最適化の一環として施すが
インラインアセンブラで記述した部分はそのままの順序で出力されて最適化
されないことが多い。

！

あげ

テンプレにある
＞ハッカーのたのしみ
は、アマゾンで評価が高いみたいですが
本当に読んで面白い本なんですか？

>>73
それはお前がビット演算を楽しめるかどうかによる。

>>73
もしもあなたが書き溜めたソースコードを持っているのなら…

ビット演算で絶対値を求めることってできますかね？
条件分岐をしないで絶対値を求めたいのですが…

>>76
このへん見てみたら？
http://www.thescripts.com/forum/thread212935.html

int y=x>>31;
return (x^y)-y;
か。
今ならcmovのほうが速いだろうけど

ふーむ…
とりあえずリンク先を参考に試してみようと思います
ありがとうございました

age

age

とにかく徹底的にｉｆ文使いたくないんだけど、
根本的に排除する方法ってないんですか？
こういう場合はできるよってのがあったらそれも知りたいです。
もうビット演算のこと以外考えたくないんです。

>>82
論理回路にｉｆ演算器はない。

if(a){
　x;
} else {
　y;
}

⇒

switch(a){
default:
　x;
　break;
case 0:
　y;
}

じゃあ僕は条件分岐と一生付き合わなきゃいけないんですか？
一生、縁が切れないんですか？？
もう勘弁しいてほしいんです。
ソース読みにくいのってみんなｉｆ文の所為じゃないですか。
この絶望のまま生きていたくない。

並列計算がうまくいかないのだってきっと条件分岐のせいですよ。
諸悪の根源と思っていますよ、もう。

ところで、論理シフトとかってあれは論理演算が関係してるんですか？

if(a>b){
　x=c;
} else {
　x=d;
}

x=(a>b)*c;
x+=!(a>b)*d;

こんな感じかな？
ビット演算じゃ無いけど

if(a){
　x;
} else {
　y;
}

⇒

n_if(a){
　x && a || y && !a;
}

平凡にジャンプテーブル
void f();
void g();
int hoge;

  before:
if (hoge != 0)
  f();
else
  g();

  after:
typedef (*func_t)();
func_t table[] = {f, g};
table[hoge != 0]();

関数コールのペナルティ＞＞＞分岐予測ミスのペナルティ


d = a ? b : c;

とかでも使えば？組み込みのCMOV命令に展開してくれたりするし
SIMD系の命令セットは比較命令はマスク生成のことが多い

P4だと、テーブル参照方式はペナルティが信じられんほど凄い。
命令20ぐらいをズラスラ書いたのより、テーブル参照1つの方が遅かったりする。

最近それ経験した。
switchで振り分けた方が遥かに速かったわ。恐るべし分岐予測。

>>82はPS3かなんかの開発やらされてるゲームプログラマなんじゃね？

もうジャンプするのも嫌になりました。
ｉｆ文なしのジャンプなしで何とかならないでしょうか？？

てきとーに制限つけてその条件内で考えさせたいだけでしょ。

age

sub a, b
adc pc, a

あげ

あけまして、おめでとうごｚぁいます

要は皆さんパズル好きだと

プログラミング自体が、言語変わってもパーツの組合せのパズルに過ぎない訳で。

>>82
>根本的に排除する方法ってないんですか？
>こういう場合はできるよってのがあったらそれも知りたいです。

ビット演算以外の仕事は「引き受けない」

>82
まずプロセッサから設計した方がいいんじゃないか

>>93
cmp+jeの組み合わせがいやならsub+jneでどうだろうか。

Cです
int i;として
iが0以外なら1を、iが0なら0を返すビット演算は
i!=0以上にコンパクトにできるのでしょうか？
n = i!=0;と括弧つけてもやや読みづらいので。
(bool)iならば可読的なので喜んで使いたいのですが、Cなので残念ながら…

!!i
なんてどう？

typedef enum{false, true} bool;

(bool)i

問題は、Cではenum型にキャストした値がenum値に制限されるかどうかだね。

めんどくさい
#define TO_BOOL(x) ((x) != 0)

阿呆なマクロを使うくらいなら>105でいいじゃん。

>>108
C、C++の最適化について語るスレ
http://pc10.2ch.net/test/read.cgi/tech/1084676298/

団子ちゃん、↑こっちのスレの結果はどうなったの？
やっぱり、団子ちゃんが適当なこと吹いてただけなの？

っつーかどうしても1にしたい状況ってそんなないだろ
0/!0で充分だから

ビット演算でも高速化でもないな。

#define BITTOENNZANN(dayo) ((dayo)!=0)

これでビット演算だお^ω^

>>33
加算器ってこんな感じじゃない？(ちょっと冗長かも)

int ADD(int x, int y, int c) {
return (x | y | c) ?
(((x & 1) ^ (y & 1) ^ (c & 1))
| (ADD(x >> 1, y >> 1,
(( !(x & 1) & (y & 1) & (c & 1))
| ( (x & 1) & !(y & 1) & (c & 1))
| ( (x & 1) & (y & 1) & !(c & 1))
| ( (x & 1) & (y & 1) & (c & 1)))) << 1)) : 0;
}

誰か減算器↓

int ADD_(int x,int y){return x?ADD_((x&y)<<1,x^y):y;}
int ADD(int x,int y,int c){return ADD_((x&y)<<1|c,x^y);}
int SUB(int x,int y,int c){return ADD(x,~y,c^1);}

>>109
! がオーバーロードされてたら、二回も呼ばれることになるぜ。

オーバーロードまで考慮したら ! 二回より != の方が遅いことも
十分ありえるけどな。

64bitのビットを数えるのは外出？

>>118
ビットを数えるってのがよくあるpop関数のことなら死ぬほど既出。

あげ

レス４は絶対ここの住民だろ笑
http://pc10.2ch.net/test/read.cgi/tech/1169104637/l50

>>121
こいつのせいでビット操作のスレになってるじゃないか

ビット演算でbranch freeなmagic incrementは可能かね？

Bit Twiddling Hacks
ttp://graphics.stanford.edu/~seander/bithacks.html
こんなサイトが（英語だけど）
テンプレに入れる？

入れるのはいいけど、それまで続くんか?

コンパイル時には>>124をテンプレとしてオーバーライドします。

もうこのスレも息切れみたいだね。

だいたいビット演算ごときでときめいちゃうのは厨房までだろw
煽りぬきで

ていうか、パズルみたいなもんだろ。

さすがに、ネタ切れにて閉店でいいと思うよ。

よほど要求速度や省メモリがシビアな環境でない限りは妙な小細工はたいして必要ないもんね

int i = 20070215;

で、この i からそれぞれ 2007, 2, 15 って数字が欲しいんだけど
誰かカッコ良くビット演算使ってやってください。

>>131
実質的には除数固定で割り算を行うのと同じだから
割り算の話になるな。

0x20070215

>>131-133
それすごくもったいなくないか

たしか
日：1-31 (5bit)
月：1-12 (4bit)
年：00-99 (7bit)

で 16bit っつー表記があったな
FDとかHDのタイムスタンプとか

今なら年だけ
0000-9999 (14bit)
でも 23bit で余裕な訳だが

>>134
そんなところでビットをケチったってしょうがねぇべさ。
そのフォーマット(MS-DOSのFATだな)はタイムスタンプが2秒単位でしか記録できないしね。
#hour:5, minute:6, second:5

ねえ偉い人
１０進数を３進数に変換するコードはJAVAでどう書きますか？

↑バカ

イマイチビット演算はよくわからん

ビット演算してると脳汁が出る

大抵は無意味だけど
オナニーとしてはﾅｶﾅｶそそる

ビット演算って1や0にするだけじゃん。

だが、それがいい。

3|17 2
3| 5 2
　 1

10進数:17 -> 3進数:122

10進数から3進数への変換て、これであってる？

なんかboost::randomの使い方が良く分からないので
extern boost::mt19937 brand;
inline const float&n_rand(){
static float x;
*((unsigned int*)&x)=(brand()&0x7FFFFF)|0x3F000000;
return x;
}
とかやってる俺はkusobaka

うわっバカだ

staticいらないだろ。

bitマスクとかメンドクサイから言語レベルでbitの配列みたいに扱える
演算子があれば良いんだけどな。
STLやboostを使っても型変換が必要だし。

ビットフィールド？

static を除去するなら、戻り値は const float & ではなく float にすべきでもある。
ところで、乱数の範囲はそれでいいのか？
２進表現で0x3f800000 から 0x3fffffff にして、そこから 1.0f を引くと [0..1) になって使いやすいと思うが。

floatの表現がIEEEに合致するってのは保証されてるんだっけ？

うんにゃ、されてない

だが、それがいい

32bitのエンディアンの変換てどうすればいい？

ごめん、よく考えたら大したことなかった。
これでOKだ。
x = ( ( x >> 8 ) & 0x00ff00ff ) | ( ( x << 8 ) & 0xff00ff00 );
x = ( ( x >> 16 ) & 0x0000ffff ) | ( ( x << 16 ) & 0xffff0000 );

単に
x = (x & 0x000000ff) << 24 | (x & 0x0000ff00) << 8
| (x & 0x00ff0000) >> 8 | (x & 0xff000000) >> 24;
と書いては何かまずいの？

152の方法だと1行目で算出したxを2行目で使っているので
1行目の処理と2行目の処理の並列性が無いし、マスク用の
定数が4バイトの2つ、3バイトの1つ、2バイトの1つで、
どのCPUを想定しているのかは知らないけど、普通は
上の方法のマスク定数より長いコードになるのでは。

24回のshiftが16回のshiftより時間がかかる状況なら
上の方法は好ましくないし、エンディアン変換のビット長が
64bitなら152の方法のほうが良いように思うが。

普通に共用体でやった方がエレガントで早いと思いますが。。

正直これでいいや。
ttp://msdn2.microsoft.com/ja-jp/library/a3140177(VS.80).aspx

>>155
?

あげ

任意のビット数のシフトやローテートてなんで１クロックで実行できねーの？
連続した場合ね。

1024bitとか？

そもそも1クロックで実行っていつの時代のどのCPUの話だよ
30年前の8bit時代から頭の中進歩してないオジサマ丸出しだねw

しかも昔の8bitマイコンだって命令サイクルと実クロックは別物だしね

なんか言いたいんだろうけど、何を言いたいのかさっぱりわからん。

知ったか厨の典型だな。(w

あげ

a

1Bit CPUの可能性について語れないのは素人。

cmos 4000 シリーズの事か？

MC14500　か

コネクションマシンか？

バイトの縛りがうざいんだよ

22時以降はダメとか?

ざぶんとん

>どっちかのbitが立ってることを確認するために
>if(hoge & 0x000000C0)
>みたいな書き方出来ると思うのですが
>両方のbitが立ってることを確認したければ
>if(hoge & 0x000000C0 == 0x000000C0)
>って書くしか方法ないですか？

以下から正しいものを選べ

1) if(hoge & 0x000000C0 & 0x000000C0)
2) if((hoge & 0x000000C0) & 0x000000C0)
3) if(!((hoge & 0x000000C0) ^ 0x000000C0))
4) if((hoge & 0x00000080) && (hoge & 0x00000040))
5) if(~(hoge | ~0x000000C0))
6) if(~(~hoge | ~0x000000C0))

(hoge & 0x000000C0) == 0x000000C0 が一番速いだろう。

#include <stdio.h>

#define MASK 0x0000C0C0

int bittesta(int hoge)
{
if((hoge & MASK) == MASK){
return 1;
}else{
return 0;
}
}

int bittestb(int hoge)
{
if(!((hoge & MASK) ^ MASK)){
return 1;
}else{
return 0;
}
}

int main(int ac, char **av)
{
int hoge = 1234;
bittesta(hoge);
bittestb(hoge);
return 0;
}

_bittesta:
pushl %ebp
movl %esp, %ebp
subl $4, %esp
movl 8(%ebp), %eax
andl $49344, %eax
cmpl $49344, %eax
jne L10
movl $1, -4(%ebp)
jmp L9
L10:
movl $0, -4(%ebp)
L9:
movl -4(%ebp), %eax
leave
ret
_bittestb:
pushl %ebp
movl %esp, %ebp
subl $4, %esp
movl 8(%ebp), %eax
andl $49344, %eax
cmpl $49344, %eax
jne L13
movl $1, -4(%ebp)
jmp L12
L13:
movl $0, -4(%ebp)
L12:
movl -4(%ebp), %eax
leave
ret

>>172 が正解なんだけど
いまどきのコンパイラは
>>171 (3) で書いても
最適化されて >>172 になってるんだね

ど素人です。質問があります。

例えば1か0が格納される変数(Aと仮定)のスイッチ切り替えの場合

【例①】
if(A == 1)
{
A = 0;
}
else
{
A = 1;
}

【例②】
A = A ^ (0 + 1);

この場合早いのはやはり例②なのでしょうか？

A ^= 1;

が速い。まあ、例２と同じだあな。

>>177
有難うございました。

SUBR #n 　　　Acc = n-Acc を持ってるCPUだと
A　=　1-A　

のが速かったりするぞ

>>177,179
いや、今回は1と0で設定されてるけどほんとは3と5かもしれないだろ
そういう場合ってやっぱA ^= 1;とかA = 1-Aより

A ^= (3 + 5);のほうが正解なんじゃないか？

1と0ならA = 1-Aとかでもいいんだけどな

A ^= 8;
？？？？？？？？？？？？？？？？？？？？？？？？？？？？


Aには1か0が格納されるって最初の条件で確定してるんだが

>>181
汎用性を高めるって意味だよ

いや8はおかしいだろ常識的に考えて

A変数に1か0だけの設定なら

A ^= 1;でいいと思うが

A変数に3か5が入ってる設定だと

A ^= 5;じゃダメだろ？

だったらどちらにでも応用できる

A ^= (1 + 0);
A ^= (5 + 3);

がいいんじゃないかって話をしたかっただけだ。

8じゃ最下位ビットはトグルできません＞＜

じゃあ7だこの野郎

ちなみに俺の回答は
A = ~A;

工ｴｴｪｪ(´д`)ｪｪｴｴ工

俺は今赤面しながら画面に張り付いてるｗｗｗｗｗｗｗｗｗｗ
確かに8じゃ無理だったｗｗｗｗｗｗｗｗｗ

>>187だと「1」にならないね。
仮に全ビット使う場合の話。
信号制御用の1ビットレジスタをこれで操作してたような。


0か1かならこっちのほうが素直か
A = !A;

3 と 5 のトグルなら A ^= 6; だな。
要するに A ^= (3 ^ 5);

拡張して　0,1,2 のトグル a=(a+1) % 3 とか 0～9 での循環a=(a+1) % 10とかになると途端に難しくなるな

WORD wに0x0001が含まれていて0x0010が含まれてない、の結果をBOOL bに納める式は
どう書くと一番短いですか？

b = (w & 0x0011) == 0x0001;

if ((w && 0x0001) == 0x0001)
{
if ((w && 0x0010) != 0x0010)
{
b = TRUE;
}
else
{
b = FALSE;
}
}

>>194
ありがとん

a:= a +1;
a:= (a+ (a shr 2) ) and 3;

これだと 1,2,3の循環になるな

A ^= (3 ^ 5);

1001
1000
0000
0001
0011
0010
0110
0100
0101
0111

　　　　　　　ヾ　 /　　　　＜ 仮面ﾗｲﾀﾞｰ555が＞
　　　　　　,. -ﾔ'''ｶｰ､　　　/Y⌒Y⌒Y⌒Y⌒Yヾ
ー―ｧ　　/r⌒|:::|⌒ヾ
　 _ノ　オ{（　　|0|　　）} オｵｵォォｫｫ！！！！！
　　　　__,ヽ,ヾ,_|V|,_ノ､/ ,r-,,=
　　　,゛＝=ゝ_ＶiＶ_ノ~i/　〃 `ー―-､
　　 / 　/⌒`//´⌒c/＾＾＾ )））)))))））
,,―ｲ　 {ｰ''"~{ {~゛`ー`/'`'~/ー--―'
）） 　　,./ゝ＿/∧ゝ＿ノ　　ﾉ
ー''"　　｜ﾛ　　ﾛ　　　　｜
人,_,人,_,人,_,人,_,人,_,
＜適当な番号をゲット!!＞

あまり適当な番号には見えない件について

0xC8

丁度256円になります。

ポイントはお付きしますか？

いいえ、彼はペンです。

char v;
if(v){ ..... }

vのビット列が [10000000] と [00000001]
ではやっぱり前者の方が早いんだろうか

最適化や前後のループや分岐予測によるだろ…常識的に考えて…

嫌な答え方だな

感じないわ。

痛くないわ。

五寸釘はイヤだろ・・・・常考

ごっすんごっすん五寸釘ー

そっちかよクソ

あいーん

効率的では無いけど少々トリッキーなJavaのコード。数列の解説は面倒なので略。

float[] p = {
0.000f, 0.000f, 1.000f, 5.373f, 0.000f, 0.998f, 4.989f, 0.000f, 1.075f, 5.000f, 0.000f, 0.000f,
0.000f, 5.373f, 0.998f, 4.865f, 4.865f, 0.951f, 4.970f, 2.370f, 1.160f, 5.000f, 1.326f, 0.000f,
0.000f, 4.989f, 1.075f, 2.370f, 4.970f, 1.160f, 3.700f, 3.700f, 0.179f, 4.473f, 2.598f, 0.000f,
0.000f, 5.000f, 0.000f, 1.326f, 5.000f, 0.000f, 2.598f, 4.473f, 0.000f, 3.536f, 3.536f, 0.000f,
};
float[] q = new float[384];
int i,j,k;
for(i=0;i<8;i++) {
k = (((i>>>2)^(i>>>1)^i)&1)*12;
for(j=0;j<16;j++) {
q[i*48+j*3+0] = ((i&1)==0)?p[(j^k)*3+0]:-p[(j^k)*3+0];
q[i*48+j*3+1] = ((i&2)==0)?p[(j^k)*3+1]:-p[(j^k)*3+1];
q[i*48+j*3+2] = ((i&4)==0)?p[(j^k)*3+2]:-p[(j^k)*3+2];
}}
for(i=0;i<32;i++) {
for(j=0;j<12;j++) { System.out.printf("%+6.3ff,",q[i*12+j]); }
System.out.print("\n");
}

+0.000f,+0.000f,+1.000f,+5.373f,+0.000f,+0.998f,+4.989f,+0.000f,+1.075f,+5.000f,+0.000f,+0.000f,
+0.000f,+5.373f,+0.998f,+4.865f,+4.865f,+0.951f,+4.970f,+2.370f,+1.160f,+5.000f,+1.326f,+0.000f,
+0.000f,+4.989f,+1.075f,+2.370f,+4.970f,+1.160f,+3.700f,+3.700f,+0.179f,+4.473f,+2.598f,+0.000f,
+0.000f,+5.000f,+0.000f,+1.326f,+5.000f,+0.000f,+2.598f,+4.473f,+0.000f,+3.536f,+3.536f,+0.000f,
-0.000f,+5.000f,+0.000f,-1.326f,+5.000f,+0.000f,-2.598f,+4.473f,+0.000f,-3.536f,+3.536f,+0.000f,
-0.000f,+4.989f,+1.075f,-2.370f,+4.970f,+1.160f,-3.700f,+3.700f,+0.179f,-4.473f,+2.598f,+0.000f,
-0.000f,+5.373f,+0.998f,-4.865f,+4.865f,+0.951f,-4.970f,+2.370f,+1.160f,-5.000f,+1.326f,+0.000f,
-0.000f,+0.000f,+1.000f,-5.373f,+0.000f,+0.998f,-4.989f,+0.000f,+1.075f,-5.000f,+0.000f,+0.000f,
+0.000f,-5.000f,+0.000f,+1.326f,-5.000f,+0.000f,+2.598f,-4.473f,+0.000f,+3.536f,-3.536f,+0.000f,
+0.000f,-4.989f,+1.075f,+2.370f,-4.970f,+1.160f,+3.700f,-3.700f,+0.179f,+4.473f,-2.598f,+0.000f,
+0.000f,-5.373f,+0.998f,+4.865f,-4.865f,+0.951f,+4.970f,-2.370f,+1.160f,+5.000f,-1.326f,+0.000f,
+0.000f,-0.000f,+1.000f,+5.373f,-0.000f,+0.998f,+4.989f,-0.000f,+1.075f,+5.000f,-0.000f,+0.000f,
-0.000f,-0.000f,+1.000f,-5.373f,-0.000f,+0.998f,-4.989f,-0.000f,+1.075f,-5.000f,-0.000f,+0.000f,
-0.000f,-5.373f,+0.998f,-4.865f,-4.865f,+0.951f,-4.970f,-2.370f,+1.160f,-5.000f,-1.326f,+0.000f,
-0.000f,-4.989f,+1.075f,-2.370f,-4.970f,+1.160f,-3.700f,-3.700f,+0.179f,-4.473f,-2.598f,+0.000f,
-0.000f,-5.000f,+0.000f,-1.326f,-5.000f,+0.000f,-2.598f,-4.473f,+0.000f,-3.536f,-3.536f,+0.000f,

+0.000f,+5.000f,-0.000f,+1.326f,+5.000f,-0.000f,+2.598f,+4.473f,-0.000f,+3.536f,+3.536f,-0.000f,
+0.000f,+4.989f,-1.075f,+2.370f,+4.970f,-1.160f,+3.700f,+3.700f,-0.179f,+4.473f,+2.598f,-0.000f,
+0.000f,+5.373f,-0.998f,+4.865f,+4.865f,-0.951f,+4.970f,+2.370f,-1.160f,+5.000f,+1.326f,-0.000f,
+0.000f,+0.000f,-1.000f,+5.373f,+0.000f,-0.998f,+4.989f,+0.000f,-1.075f,+5.000f,+0.000f,-0.000f,
-0.000f,+0.000f,-1.000f,-5.373f,+0.000f,-0.998f,-4.989f,+0.000f,-1.075f,-5.000f,+0.000f,-0.000f,
-0.000f,+5.373f,-0.998f,-4.865f,+4.865f,-0.951f,-4.970f,+2.370f,-1.160f,-5.000f,+1.326f,-0.000f,
-0.000f,+4.989f,-1.075f,-2.370f,+4.970f,-1.160f,-3.700f,+3.700f,-0.179f,-4.473f,+2.598f,-0.000f,
-0.000f,+5.000f,-0.000f,-1.326f,+5.000f,-0.000f,-2.598f,+4.473f,-0.000f,-3.536f,+3.536f,-0.000f,
+0.000f,-0.000f,-1.000f,+5.373f,-0.000f,-0.998f,+4.989f,-0.000f,-1.075f,+5.000f,-0.000f,-0.000f,
+0.000f,-5.373f,-0.998f,+4.865f,-4.865f,-0.951f,+4.970f,-2.370f,-1.160f,+5.000f,-1.326f,-0.000f,
+0.000f,-4.989f,-1.075f,+2.370f,-4.970f,-1.160f,+3.700f,-3.700f,-0.179f,+4.473f,-2.598f,-0.000f,
+0.000f,-5.000f,-0.000f,+1.326f,-5.000f,-0.000f,+2.598f,-4.473f,-0.000f,+3.536f,-3.536f,-0.000f,
-0.000f,-5.000f,-0.000f,-1.326f,-5.000f,-0.000f,-2.598f,-4.473f,-0.000f,-3.536f,-3.536f,-0.000f,
-0.000f,-4.989f,-1.075f,-2.370f,-4.970f,-1.160f,-3.700f,-3.700f,-0.179f,-4.473f,-2.598f,-0.000f,
-0.000f,-5.373f,-0.998f,-4.865f,-4.865f,-0.951f,-4.970f,-2.370f,-1.160f,-5.000f,-1.326f,-0.000f,
-0.000f,-0.000f,-1.000f,-5.373f,-0.000f,-0.998f,-4.989f,-0.000f,-1.075f,-5.000f,-0.000f,-0.000f,

誰かエスパーしてくれ

新手の荒らしだろ、スルーよろ。

k = (((i>>>2)^(i>>>1)^i)&1)*12;
は
k = ((i>>>2)&4)*12;
と等価じゃない？

k = (((i>>>2)^(i>>>1)^i)&1)*12;
は
k = ((i>>>2)&1)*12;
と等価

おいおい、不等号3つって……

System.out.printfって何だよ
オブジェクト指向すげえよ

>>>220-221
^は排他的論理和、>>>は符号無し右シフト、&は論理積なので、
k=(((i>>>2)^(i>>>1)^i)&1)*12はi=1,2,4,7の時にk=12、i=0,3,5,6の時にk=0となる。
全然等価じゃねーぞ。

エスパー困難なコードですが、一番意図の分かりにくい部分だけ解説。

k = (((i>>>2)^(i>>>1)^i)&1)*12;
上の文は、iのパリティがevenであればk=0、oddであればk=12とする処理を行う部分ですが
iの値域が0～7に限られるため、パリティの計算は下3bitに対してのみ行っています。
k = (Integer.bitCount(i)&1)*12; とする手もありますが、今回は先のように書きました。

p[0]～p[15]を4x4の行列と見た場合に、q[]にその値をコピーする
for(j=0;j<16;j++) { q[j] = p[j^k]; }
の処理はkの値によって以下のような振る舞いの変化をします。
k=0：そのまま、k=3：列を逆順に入れ替え、k=12：行を逆順、k=15：行・列ともに逆順

そこまで式が込み入ってたら、テーブルの方が速くないかな。
まあ、環境によるとは思うが。

あげ

ある変数の中でビットが必ず一つだけ立っているとき
そのビットの位置（左右どちらからでもよい）を求めたいのですが
↓のNTZやNLZを求めるアルゴリズムを使うのよりも高速にできませんか？
http://www.nminoru.jp/~nminoru/programming/bitcount.html
立っているビットの数が一つという条件があるので
何か工夫できないか考えたんですけど思いつきません。

どっかで聞いたような質問だな・・・

memcpyよりも高速にコピーできる高速memcpyを作りたいのですが
何か参考になる方法ってありますか？

>>230
memcpyより高速な手法が存在するとしたら、世の中のmemcpyはその高速
な手法を使うんじゃない？

>>230
ビット単位で転送するという話でもない限り、スレ違い。

>>231
いいえ。

前スレのログってどこかにある？

あ、あったあった。
http://p2.chbox.jp/read.php?host=pc8.2ch.net&bbs=tech&key=1123918075&ls=all
ここの377に似たような質問があるね。

>>228
ビット位置を持って回ることを検討したか?

>>230
つ [ゼロコピー]

ビット位置を持って回るのは難しいと思いました。
ビットはこんな風に複数のビットが立ってる変数から取り出してます。
UInt32 bits;
...
while(bits)
{
UInt32 bit = bits&(-bits);
UInt32 bit_position = get_bit_position(bit);
...
}
で、このget_bit_position()の部分を作りたいのですが・・

ちょっと>>235を読んできます

とりあえず>>235の430でやってみます。
みなさんありがとうございました。

24xx32～24xx512 までのシリアルEE-PROMというのは
pageというのを持っていてページサイズ内なら一度に書き込みが出来ます
ページサイズは8～256まで２のべき乗で、ROMタイプによって異なります。
今、EE_write(adr , size, dt[] ) という関数があって、この関数はページサイズを認識しません。
そこでこのラッパを作りたいのです
pagesize, ADR, SIZE , *p

if( (ADR ^ (ADR + SIZE -1)) & (0xFFFFu-(pagesize-1) ) ){　一度に書ける }

分割しなければいけない場合
ADR ～ (ADR | (pagesize-1) ) が最初に書く領域　

というふうに考えたのだけど、ループが格好良く書けないの。

自己レス
結局こうやった

while(( (ADR ^ (ADR+SIZE-1)) & (0xFFFFU-(pagesize-1)) ) ){
　ct = (ADR | (pagesize-1))+1 -ADR;
　EE_write(ADR, ct , p);
　p　　+= ct;
　ADR　+= ct;
　SIZE -= ct;
}
EE_write(ADR, SIZE , p );

格好良いかどうかは主観だという良い例。

>>241
普通に書くとこんな感じ？

    unsigned tail = adr + size;
    unsigned ct = pagesize - adr % pagesize;

    while (adr + ct < tail) {
        EE_write(adr, ct, dt);
        dt += ct;
        adr += ct;
        ct = pagesize
    }
    if ((ct = tail - adr) != 0)
        EE_write(adr, ct, dt);

>>241って、SIZEに 0 を指定されると大変なことになりそうだな。

汚いJavaコードコンテストの会場はこちらですか？

いいえ、ここはJavaを知らない244が居るスレです。

面白くない　失せろ

エンディアンの変換を共用体でやるのってどうやるんですか？

バイトオーダーは詳しくないが
int, int って並びなら、
1, 2, 3, 4, 5, 6, 7, 8 が
4, 3, 2, 1, 8, 7, 6, 5 ってなるだけで
8, 7, 6, 5, 4, 3, 2, 1 にはならないのでは？

こうですかわかりません＞＜

typedef union {
　　uint32_t wd;
　　uint8_t bt[4];
} HogeType;


HogeType a, b;
a.wd = src;
b.bt[0] = a.bt[3];
b.bt[1] = a.bt[2];
b.bt[2] = a.bt[1];
b.bt[3] = a.bt[0];
dest = b.wd;

ヤツはダンゴさんじゃない

共用体って、本当はそういう風に使っちゃダメなんだよな。
規格違反。
まあ、そう使えないコンパイラはないと思うけど。

おいおい共用体をそういう風に使わずにほかにどんな用途があるって言うんだアホかw

使ってはいけない理由があるからそう決められているんだろ。
その理由が皆目検討つかないが。

>>243
ありがとう。参考になった。
でも、そのままだと最後の書き込みサイズが正しくなかったよ。

>>252,>>253
共用体のメンバのうち T 型の a というメンバに値が格納されているときは
U(!= T) 型の b というメンバの値は T 型の a に依存し、U 型の値としては
不正と見なされるため b を通してのアクセスは未定義の動作となる。


ではなぜ共用体が存在するのかというと、おそらく原始的なポリモーフィズムの
実現の為。

ある変数が複数通りの型（ここでは T と U とする）の値を受け入れる可能性が
あるとき、構造体のような、型の異なる複数の変数を用意するのは非効率のため
単一の変数で複数の型を扱える共用体を使う。

もっとも、C++では T 型と U 型の基本クラス V 型を定義して、V 型の参照として
T 型にも U 型にも（もちろん V 型にも）正規にアクセスできるので、共用体は
不要になってしまった（のだろう、たぶん）。

共用体はこういうことのためにある。

enum Variant_Type {
  VARIANT_INT,
  VARIANT_DOUBLE,
  VARIANT_CHAR,
  VARIANT_STRING
};
struct Variant {
  union {
    int i;
    double d;
    char c;
    char *s;
  } value;
  enum Variant_Type type;
};

/* var->type で分岐して、その内容を表示する関数 */
void Variant_show(const struct Variant *var) { ... }

int main(void) {
  Variant var;

  var.type = VARIANT_INT;
  var.value.i = 4;
  Variant_show(&var);

  var.type = VARIANT_STRING;
  var.value.s = "hoge";
  Variant_show(&var);
}

>>255
> もっとも、C++では T 型と U 型の基本クラス V 型を定義して、V 型の参照として
> T 型にも U 型にも（もちろん V 型にも）正規にアクセスできるので、共用体は
> 不要になってしまった（のだろう、たぶん）。

不要になってないだろ。

基本クラス云々で各種のデータを扱う処理は正規にできるようになったけど、
複数の型を同一の領域に割り付けるのは union でないとできない。

まあ、そんな機会はめったとないが。

普通わざわざそんな面倒なことしないと思いますけどねw
それで何の御利益があると思って書いてるんだろうか？
不思議な発想だとしか言いようがない

っていうか、それ多態じゃなくて多重定義でしょ？w

？

258は>>255-256宛てね

型がクラスだったりする可能性を考えると
共用体よりplacement newのほうが良いと思う。

バリアント型とか知らないのかな。
そして、それが内部的にどうなってるかとか、
そこでのコスト意識とかに至っては、全く考えた事ないんだろうね。

>>261
共用体に入れられるのはそもそも POD 型だけだが、
ポインタで保持しておくことなら可能だな。

>>262
> バリアント型とか知らないのかな。

Ｃ言語でそんなもん使う機会があまりないこととか知らないのかな。(w

いや、煽り抜きでそういう発想はちょっとないよね。

Cだとバリアント型はにっくきCOMの象徴のひとつだからトラウマが・・・ｗ

皆がどのレスについてレスしてるのか分からなくなってきた。
つーかビット演算スレでなぜ共用体…。

「そういう発想」というのは共用体をvariantとして使う発想ということかしら。

　　 { >>>>>>>>985 }
　　　 ζ
　 　　　!(+Φ＿Φ)つ√ζ
　 　 +⊂.　+ 〆∂ 　 {Ж}
　 　 "〆∂∂
　 　〆〆
　 .:"

コピペ君って馬鹿だな、まで読んだ。

>>256
でも共用体って記述した順番にメモリに保存されるかについて
仕様では未定義ですよね

>>270
当たり前だろ。

つか struct の仕様と混同してないか?

>>270
これはひどい

コンパイラコンパイラ触ってるなら、
このくらい常識だろ？

という批判と、このスレでの質問だという事を考えると、>>249　は

typedef union {
　　uint32_t *pW;
　　uint8_t *pB;
} HogeType;

HogeType a;
uint8_t w;
a.pW = &src;
a.pB[0] ^= a.pB[3];
a.pB[1] ^= a.pB[2];
a.pB[2] ^= a.pB[1];
a.pB[3] ^= a.pB[0];
a.pB[0] ^= a.pB[3];
a.pB[1] ^= a.pB[2];

みたいなのが希望って事か？

それは二重に規格違反してて、
おかしくなるコンパイラもあるらしいよ。
俺はそういうの見た事無いけど。

おかしくなるコンパイラがあるのではなく、動作が保証されないということ。
そういうコンパイラが現実にあるのかと言われても、んなこと知らん。
だが、顧客に「正常に動作することが保証されている」プログラムを提供するためには
仕様上未定義とされる書き方をしてはいけないし、意識せずしてしまったらバグとして扱われて然り。

参考までに>>274の規格違反している点を簡単に指摘してください

規格違反していても、多分 >>249 がおかしくなる処理系はないんじゃね？
逆に、規格通り書いてもおかしくなることもある。
規格違反はそれはそれで重要だけど、
実際の処理系でどうなのかという方が時に重要な事もある。
ま、コメントとか残しておいて、
移植時にすぐ検索できるようにしておくべきではあるが。

>>277
共用体の pW メンバに代入した場合、
pW の値しか正当性が保証されない。
そのため、pW に代入したすぐ後に pB を参照したとき、
規格ではその動作を保証しない。

uint32_t * と uint8_t * のアドレス表現が等しいという保証は無い。
この間のキャストで何らかの変換作業が生じる場合には、
このコードは正しく動かない。

そもそもアドレス演算は、配列要素へのポインタでしか保証されない
（配列風の参照では p[4] と *(p + 4) は等価で、
　ここには p + 4 というアドレス演算が生じる）。
ここが原因で >>274 のようなことをすると
おかしくなる処理系があるという風に聞いている。
（「ハッカーのたしなみ」 の 87 ページを参照）

ハッカーのたしなみ に一致する日本語のページ 約 104 件
ハッカーのたのしみ に一致する日本語のページ 約 26,800 件

すまんよ。まちがえた。

そもそもCの言語仕様で「未定義」な理由は、最初のバイトが最上位か最下位かはエンディアン依存だから。
逆にいうとハードに強く依存する標準仕様はあってはならない。

もちろん環境が特定できる場合なら、エンディアンの違いを理解して使うぶんにはまったく問題ない。
むしろ同一アーキテクチャでならコンパイラのABIレベルではこういう部分も互換性が保障されてないと駄目。
そもそもエンディアンなんて標準仕様外のものを扱うのに、標準仕様を持ち出すほうがおかしいと思うがね
構造体などのデータアラインメントやABIの互換性は言語の規格じゃなくて
各CPUやOSのメーカー、コンパイラメーカーなど同士の取り決めで決まる。
つーか、暗黙の共通仕様や独自仕様にたよらないとTCP/IPすら扱えないぜ。

構造体のアラインメントはC仕様では未定義だが、アラインメント不整合だと例外を起こすアーキもある。
データレイアウトを実装者で取り決める独自仕様が認められないなら、Cは危険な言語だな逆にいえば。

「仕様では未定義」は逆にいえば実装では各環境のABIに従ってきめていいということ。

>>282-283
仕様上未定義を「未定義の動作」と混同していないか。
Cは移植性を高めるため、特定の環境に依存するような仕様はほとんど盛り込まれておらず
よって指摘の通り構造体のメモリ上でのレイアウトも定義されていない。

だが、メンバに正しくアクセスできることは保証されている。

実は未定義ではなく実装依存という罠

エンディアンの変換はほぼ間違いなくできるがリトルからビッグかビッグからリトルかはエンディアン依存ってことだろ。

逆に>>349が意図しない動きをするコード吐くコンパイラって存在するなら教えてほしい。
変態のCellですら>>349が正しく動くことはABIレベルで保証されてる。
各型のレイアウトを厳密に定義してるからな。

共用体で　 ビットフィールド　を使えば、マシになるかい？

>>286
>>276
そして話題はループする。

ABIはCの言語仕様における実装依存の箇所を定めて厳密化するものなので
たとえABIの隙をかいくぐって自分の予期した挙動をさせることができたとしても
それは立派な規格違反。

あと、もし>>282さんと同一人物なら
＞そもそもCの言語仕様で「未定義」な理由は、最初のバイトが最上位か最下位かはエンディアン依存だから。
これのソースを頼む。探しているんだが、見つからない（汗

規格にないものを扱うのに規格内のルールを持ち出す馬鹿。
windows.hを使うのも規格違反だとか言い出しそうだな

厳密にはそうだな。ハンドルをポインタ型とかメチャクチャしたMSは糞。
ちなみに、規格にないものを付け加えるのではなく、規格に抜けているを補うのがABI。
本来は規格に矛盾しないABIを定めなければならない。

ところでここはビット演算についてかたるスレなのか？

ミドルエンディアンのこともたまには思い出してやってください

GUIがなくてstdioで画面入出力するようなアプリのほうが品質低いと見なすがなうちの顧客は。

「定義するな」なら違反になるが単に未定義のものに一定の動作保証をするだけなら違反じゃない。
何のために#pragmaが規格にあると思ってる。
処理系依存の拡張を、やっていいよと保証すらしてるのが規格だ。

ちなみにunion使った型変換はWindowsでは日常茶飯事だな。ULONG_INTEGERとか。
ここの住人がよく使うであろうMMXやSSEなんかはC用APIなんか、まさに共用体を使った型変換のオンパレード。
それでもパフォーマンスを求める客の「信頼」を得るためにすすんで使うものだ。

ANSI/ISO規格が絶対的に信頼されてて規格外のものは信頼されてないなんて独善的な言い分にすぎん。
getsみたいな危険な関数が野放しにされてるのはなんだね。
極論、信頼性の確保という面ではVC2005のセキュアCRT関数のほうが標準関数よりまとも。

ちなみにポインタをHANDLEという型にtypedefできるのは規定の動作。なんら問題ない。

きもちわるいなあ

エチケット袋持ってきましょうか？

いえ結構。そのまま吐きます

キッシュを食うのとエチケット袋を使うのはガキ。

「規格違反のプログラム」 は、
特定の環境では動くことが保証されてるかもしれないけど、
全ての環境で動く保証が無い。
だから、そのプログラムが特定の環境でのみ使用される事が決まってるなら、
規格違反でもその環境でちゃんと動作する事が保証されていれば問題ない。
ただ、色んな環境で使われるプログラムであれば、規格通りに作らないといけない。

つまりは要件次第の問題であって、常にどちらかでないといけないみたいな事を言うのは愚。

>>292
gets の使用は規格で推奨されていない。
未だ存在しているのは単に互換性のため。
セキュアCRT関数は安全だが、
GCC でコンパイルしたいような場合には
#if 使って GCC でも大丈夫なようにする必要がある。

あと、ハンドルで問題とされているのは、
ハンドルの値は別にアドレスではないのに
ポインタに入れるようにしている点。
ただ、これは int にしてしまうと安全性が低くなるし、
環境依存という程ちゃんと動かなくなる環境もないしで、
いい hack だと思う。

話は逸れるが、ハンドルも全てがアドレス値（ポインタ）でないとは限らない。
ドラッグ＆ドロップの処理などでGlobalAllocでメモリ確保したものを
HDROP型へキャストしてやるという事例がある。

ふうんと言われればそれまでのことだけど。

それをいうなら、そもそもポインタ（というより左辺値）だってアドレス値とは限らないでしょ？

プログラムごとに論理的なアドレス空間を持ってるんじゃないの？
昔、物理的なアドレスを使えば一意だろうと思って使ったら、見事に失敗した。

＞ハンドルの値は別にアドレスではないのに
＃ハンドルの値は別にアドレスとは限らないのに

とするか。

まあ、メンバ関数ポインタなんかは
確かにメモリアドレス以上の情報を持ってることもあるけど、
C++ における「アドレス」ってのは、
そういう情報も含むんじゃないのかな。多分。

きょうび、１つのCPUでも「アドレス」が3種類くらいあって当たり前だしなぁ

Cはアドレスの概念を抽象化したから、Cにはアドレスという概念はないと。
どっかで見た。

ところがどっこい&演算子の読み方は・・・

アドレス演算子だな。

えっ？reference operatorじゃないの？
とか思ったけどそれはC++の話でしたねすいません

ANSI C: address operator
別名: reference operator

よーしだんごやさんが燃料投下するぞー
「共用体を使った型変換は、保証されないとむしろ違反」

uint32とuint8[4]の完全なアドレス共用が保証できなければ

・各パートの先頭アドレスの一致
・char型(=1バイト)配列のデータ連続性
という規格で保証された動作に違反することになる。

断言する。
バイトオーダさえ一致すれば、共用体を使ったビット列の直接変換は保証できる。



つーか、規格にない動きまで保証されると規格【違反】なら、
Cコンパイラは現実のアーキテクチャ向けに実装された時点で違反を抱えることになり
空想の産物でなければならないことになるね。

規格外と規格違反を混同してるんじゃないの。
規格にない機能を実装したり独自の制約・動作保証をしたらいけないなんて規約は
規格に存在しない。

RubyはCで書かれてるけどオブジェクトは共用体を巧みに使うことでで実装されてるね。
それでもさまざまなプラットフォームに移植されてるけどｗｗｗｗ

最適化でどうなるかとかちゃんと考えてるか？

まあ、パーシャルリード・ライトはモダンアーキテクチャでは遅いから速度面でのメリットないし
バイトオーダーの変換に共用体を持ち出すこと自体は俺としても感心しない。
HDの洗礼受けた人間ならこんな厨コードになるだろう

uint32 bswap(uint32 n) {
n = (n >> 16 | n << 16);
return ((n >> 8) & 0x00FF00FF) | ((n << 8) & ~0x00FF00FF);
}

こんなコードを書く間にもx86なら即値が使えるとか、
PowerPCならAND-NOT命令があるから定数ロードは1個だけでいいとか
アーキの特性を考えながら組む。
速くなるか遅くなるかも実装依存。それがビット演算厨の愉しみ。



書いた後で、「PPCとx86なら組み込みのBSWAPで十分な気もしてきた」とか思うのもまた一興。

んじゃ、燃料投下。
--
template<typename Type> static inline void endian(Type & val) {
union foo {Type t; char c[sizeof(Type)];} bar = {val};
std::reverse(bar.c, bar.c + sizeof(bar));
val = bar.t;
}

x86のeaxレジスタは下位半分はaxレジスタであり、ahとalでもある
レジスタそのものが共用体なんですよ。

>>313
template<> static inline void endian<int>(int & val) {
union foo {int t; char c[sizeof(int)];} bar = {val};
char tmp = bar.c[0]; bar.c[0] = bar.c[3]; bar.c[3] = tmp;
tmp = bar.c[1]; bar.c[1] = bar.c[2]; bar.c[2] = tmp;
val = bar.t;
}
--
これくらいの特殊化しておかないとw
ついでに言うと、これをどう最適化するかがコンパイラの腕の見せ所。

若本・・・じゃなかった、CellのSPEで実行

#include <algorithm>
#include <stdio.h>
template<typename Type> static inline void endian(Type & val) {
union foo {Type t; char c[sizeof(Type)];} bar = {val};
std::reverse(bar.c, bar.c + sizeof(bar));
val = bar.t;
}
int main()
{
unsigned int i = 0x12345678;
endian(i);
printf("0x%0X\n", i);
return 0;
}

[root@ps3 age]# spu-gcc test.cpp
[root@ps3 age]# ./a.out
0x78563412

>>309
混同も何も、そもそも「規格外」とか「規格違反」とかいう用語は規格にあるのか？

%0X って意味ねー。
%08X っしょ。

64bitから8ビットだけを取り出して操作するってAESとかCamelliaではありがちな処理なんだよな。
よく最適化されたコードは、MMレジスタからpextrwで16ビットをeaxに転送した後、al, ahを使ってテーブル参照する。

気色の悪いHN付ける奴の行動パターンやそこから透けて見えるパーソナリティっていうのは、
どいつもこいつもどうしてこう画一的・類型的で凡庸なんだろうなw

恐らく本人の自己イメージはその正反対なんだろうけどさ。

凡庸乙

>>320
あなたのその発言もまた　画一的・類型的で凡庸　な事に気付いてての発言だとすれば　あなたは勇気がある。
気付いてないなら・・・・・

人間なんてみんな一緒だろ。
ハッキリいってイルカよりもマグロの方が頭いいです。
人類の知能は一億年遅れてる。

【高速化】ビット演算　0x02

俺のアナルも高速化されそうです

俺様の射精は低速化されましたが何か?

さらに角度までorz....

自分の精液を味わって飲んでみましたクセになりそうです

【下ネタ化】ビッチ猥談

>>328
なんか体調によって味とか変わってくるらしいね。調子がいいときはどんな味がするん？

ごめん、sage 忘れた。

ごめん、ぬるぽ忘れた。

ぬるぽの話題は参照の話題について直接的ないし間接的に関係のあるスレッドでしか出す事は許さん。

>>329
それを言うなら「低俗化」では?

風俗化

Jデッ化

つーかおまいらこんなことしてていいの化

ばか

珍しく最近妙にスレが伸びてると思ったら、こう言う内容だったの化

なんじゃゴラァ、おまいらバカ化

あ？

0000 0001 0011 0010 0110 0111 0101 0100
1100 1101 1111 1110 1010 1011 1001 1000

ってどんな意味のあるビット列ですか？
教えてください。

パイオニアだかボイジャーだかのレコード盤に記録されてる奴？

Gray Codeだな

entity GRAY_CODE_COUNTER is
generic( N : integer := 4 );
port( CK, RESET : in std_logic;
Y : out std_logic_vector(N-1 downto 0));
end GRAY_CODE_COUNTER;
architecture BEHAVIOR of GRAY_CODE_COUNTER is
signal GRAY, COUNT : std_logic_vector(N-1 downto 0);
begin
process ( RESET, CK ) begin
if ( RESET = '1' ) then
COUNT <= (others => '0');
elsif ( CK'event and CK = '1' ) then
COUNT <= GRAY;
end if;
end process;
process (COUNT)
variable BIN : std_logic_vector(N-1 downto 0);
begin
BIN(N-1) := COUNT(N-1);
for I in N-2 downto 0 loop
BIN(I) := BIN(I+1) xor COUNT(I);
end loop;
BIN := BIN + 1;
GRAY(N-1) <= BIN(N-1);
for I in N-2 downto 0 loop
GRAY(I) <= BIN(I+1) xor BIN(I);
end loop;
end process;
Y <= COUNT;
end BEHAVIOR;

ううまま　うままう　うまう　うままう

>>342
たとえば、機械類なんかの位置あわせの目的で　センサーを配置する時に
４入力あれば１６箇所の位置を特定できるわけだけど
同時に２つのセンサーが変化するようになってると巧くゆかない。
そこで移動につれて、一つしかセンサーが変化しないような配置方法を考えたのがそのコード。

要するに>>342は
01 02 03 04 05 06 07 08
09 10 11 12 13 14 15 16
って意味

>>347-348が理解できない

ばっかー

2ビットのグレイコードは、2相エンコーダと呼ばれてる。　機械式のマウスなんかで使われている。
　00 01 11 10　この順番で動けば 順方向　逆方向なら　00 10 11 01 と動くので区別出来る

2進数 00 01 10 11 でいいじゃないと思うだろうけど　これだと一度に2ビット変化する箇所が2度出来る
センサーの取りつけに物凄い精度が要求される事になり安価なマウスに採用出来ない

ハミング距離でぐぐるといいよ

上位ビットから順に加算して途中でやめても、下位ビットの影響がそれより上に及ばない、っていう利点もある。

>>353
それ、具体的に教えて。

56の余りを求めるビットマスクはどのように書けばいいのでしょうか？

商か剰余を求めるビット演算を生成する CGI か何かを昔見かけたような気が・・・。
どこだっけかな・・・。

56の余りってなにさ?

x % 56でも計算したいんじゃね？

x % 56だと　２のベキ乗じゃないからビット演算1発では出来ないな
ttp://www.tensyo.com/urame/date/dayTips.shm
ここの後ろの方にビットマスクと繰り返し演算で剰余を求める方法がある

定数での除算って、こんなに繰り返し必要だったっけ？
３、４回の演算で書けたような気が・・・って、俺の記憶違いか？

それ、もしかしたら、２のべき乗での除算？

いや、それなら１回でいけるし。

あれ？ 乗算だっけ？

ああ、何か乗算だった気もしてきた。スマン。

2^N>=b となるNを求める(2^N == 1<<N) ・・・・・　N=6　2^N=64
B=2^N-b ・・・・・・ 64 -56　= 8
C=2^N-1 ・・・・・・ 64 - 1 = 63
while(a>=2*b){ B *(a>>N) + a&C };

while(a >=56*2 ){ 8 *(a>>6) + a&63 };

while(a >=56*2 ){ ( (a>>6) <<3 ) + a&63 };

1ループで3ビット改善するから 32bitなら　最大10回ちょっとのループか

56*73 =4088 で 2^12-8 だから
a = ( (a>>12)<<3 ) + a & 4095; を　前段でやれば改善するんじゃないかな　

最近のコンパイラは定数の割り算は掛け算に置き換えるね。
56で割るロジックをコンパイルしたら、-1840700269を掛けた後に
ビットシフトと足し算をしていた。それ以上追っかけるのはパス。

インテルのコンパイラで a=a%56 の出力はこんな感じ(aはunsigned int)。
LARGE_INTEGER li;
li.QuadPart = UInt32x32To64(a>>3,0x24924925);
int d = li.HighPart;
a -= ((d<<3)-d)<<3;

aがsigned intの場合は、もう少し複雑。

なるほど、>366の数値が0x92492493だからシフト量が違う同じビットパターンなのか。

でもまあPCのCPUみたいに掛算が高速だったらって前提だな。
1チップとかだと　掛算はビットサイズに応じたサイクル数かかるし
掛け算持ってないＣＰＵもあるし

大丈夫、そういうCPUは割り算も遅い。

a = ( (a>>18)<<3 ) + a & ((1<<18)-1);
a = ( (a>>12)<<3 ) + a & 4095;
a = ( (a>>9)<<3 ) + a & 511
a = ( (a>>6) <<3 ) + a & 63;
a = ( (a>>6) <<3 ) + a & 63;
while(a>=56) a-=56;

これならどうだろ？

演算子の数が20を超えてるな。
素直にdiv使った方が速いかもしれない。

もうちょっとバランスをうまく取れば、1行減らせるかもな

結局　3bit　単位だからなあ

最初は
a = ( (a>>15)&(-7) ) + a & ((1<<18)-1);
か
a = ( (a>>12)&(-7)) + a & ((1<<15)-1);
のどっちかで、どっちも32->18.4bit
次は
a = ( (a>>6)&(-7) ) + a & 511 　でも12.5bit
a = ( (a>>9)&(-7) ) + a & 4095; でも12.5bit

あとは3ビットづつしか落とせない。　無理

あ、
a = ( (a>>18)<<3 ) + a & ((1<<18)-1);
a = ( (a>>12)<<3 ) + a & 4095;
a = ( (a>>6) <<3 ) + a & 63;
a = ( (a>>6) <<3 ) + a & 63;
while(a>=56) a-=56;
とやれば、最後の　while はせいぜい3回のループでいいか

>>372
div 命令は、持っていてもbit数のサイクルかかるのが殆どだよ。　だから >>366-367 のような最適化がされるんだし

ただ PC の場合はレイテンシがかかるだけだから、divを使った方が速いかもしれないな。

>>367
ここまでしても idiv より速いのか・・・。

Pentium II およびPentium III プロセッサの実行ユニット

整数乗算は　レイテンシ4、スループット1/ サイクル
除算は浮動小数点ユニットで行われ
FDIV 命令　レイテンシ: 単精度17 サイクル、倍精度36 サイクル、拡張精度56 サイクル

だから、桁違いにレイテンシが大きい。

浮動小数点ユニットで行われるのか？！

だって　整数乗算ユニットってのはブロック図にあるが、　整数除算ユニットってのはどこにも無いだろ？

除算ってのはコストのわりに利用頻度が少ないから、どうせ浮動小数点ユニットもってるからそっちで計算させてるのさ
仮に、整数演算ユニットで除算をしたとしても、結局32サイクルはかかるし、その間加減算比較ユニットの一つが潰れてしまうからな

そうだったのか・・・。
そら遅いわな。

>>381
これ以上はスレ違いになるがつっこませてくれ。
浮動小数点ユニットがIEEE754（だったっけ）で処理する場合、単精度で23ビット、倍精度で52ビットの精度だろ。
被序数が32ビット整数ならともかく、64ビット整数の除算は精度の問題上アウトだぞ。

>>383
Intel 系の浮動小数点ユニットは
拡張倍精度（80ビット/仮数部64ビット）で行われてるから大丈夫。

>>384
まじか！と思って何年も開いていない重たいバインダーを紐解いてみたら、たしかにそう書かれているな。
しかも本当は63ビット精度なのに、ケチりビットをケチらない荒技で対処してるし・・・。
そのうえx87コプロに限ればつねに拡張倍精度で計算されることになってたりして、もうね、馬(ry。

56 = 7*2^3 だから

x % 56 = (x % 7)<<3 + (x & 7)

x/7 を round(2^32/7 )>>32 で近似したのが >>367

しかし、1/7って面白いなぁ。10進だけでなく16進でも綺麗な循環小数になるんだな。

もしかして >>375 のような事しても idiv 使うより速いって事はありえるのか？

>>388
実際に速度を比較してみれば？

Cの場合、&より+の方が優先順位が高いので、
>>375の&演算には括弧が必要だね。

そうだね。

やってみた。

function getRDTSC: int64;
asm　　　DW　　$310F //RDTSC
end;
var ww:Integer;
procedure TForm1.Button1Click(Sender: TObject);
const CNT=100000;
var t1,t2,t3:int64;
i,a:Integer;
begin
t1:=getRDTSC;
　for i := 1 to CNT do　begin
　　a := i;
　　a := ((a shr 15) and 7) + (a and ((1 shl 18) - 1));
　　a := ((a shr 9) and 7) + (a and 4095);
　　a := ((a shr 3) and 7) + (a and 63);
　　a := ((a shr 3) and 7) + (a and 63);
　　while a >= 56 do a := a - 56;
　　ww:=a; {mod と同じになるように}
　end;
t2:=getRDTSC;
　for i := 1 to CNT do　ww:=i mod 56;{ローカル変数に代入すると最適化で消えるので}
t3:=getRDTSC;
Memo1.Lines.Add(format('T2-T1 %10d',[t2-t1]));
Memo1.Lines.Add(format('T3-T2 %10d',[t3-t2]));
end;
---------------
T2-T1 1610740
T3-T2 4317497
間違いでなければ　mod 命令より速い

そうだね。

上の and 7 は　 and -8 の間違いだった

でも、掛算を使うのはさらに半分だった。

for i := 1 to CNT do
begin
a := i shr 3;
asm
　　 mov eax,$24924925;
　　 IMUL a;
　　 mov a,EDX;
end;
ww := i - ((a * 7) shl 3);
// if ww<> (i mod 56) then Memo1.Lines.Add( 'Err');
end;
t4 := getRDTSC;
T2-T1 169613675
T3-T2 436034967
T4-T3 86040347

　結局 idiv : ビット演算 : 掛算の　重さは　およそ　5 : 2 : 1 だった。

ビット演算　思ったよりガンバレるな。

これを高級言語で書いたら他の人に白い目で見られるだけならまだいいんだけど
ひどい場合は書き直しすら命じられまする(´・ω・`)

そうだね。

>>396
高級言語の目的の一つが可読性の向上だからね。
コメントで解説いれても却下される場合すらあると思うよ。

除算命令がないCPUなら有効だろうけど
x % 60 が欲しい時とか、いちいち変換が大変だよな

導出は機械的なプロセスだから、スクリプトみたいなのでサクッと求めるといいと思う。
可能なら、最適化の一環としてコンパイラに組み込むのがベストだが。

だから、掛け算化はgccでもやってるって。

>>401
ほんとにやってる？やらない場合も多いけど
絶対さぼってる

昔のx86みたいにALUしかないCPUはそういう風にやってたのかぁ、勉強になりました。

>>403
定数割り算の掛け算化が行われない例があれば、逆に教えて欲しい。
まさか、最適化オプションを指定しないとしてくれないなんて言わないよね。

>>404
深く考えず単純に引き算かと
今考えると空恐ろしいやり方だｗ

>404は>402宛てなんだろうなぁ。それはいいけど、>405は何を言いたいのだろう……

きっと8086には除算命令が無いと思ってるんだろう。

Pen3では除算を浮動小数点ユニットでされるというのを見て、
浮動小数点ユニットが無い時には除算も無かったと思ったのかな

除算そのものはシフト減算比較の繰り返しで出来るから
サイクル数さえ必要なだけかければマイクロプログラム方式ならそうコストかからない
掛け算と変わらない。

>>406
あ、ほんとだね
>>407,408
んにゃ、引き算の連続で商余求めてたのかなと

これは固定での剰余だから高速化出来るのであって
変数での剰余になると、結局コードで書いても加え戻し法(復元法)とかになるので
除算命令使った方がやっぱり速い。

DSP(やCell)では逆数をニュートン法で求めるのが定番

8086で除算命令使うとCPUの方で乗算とシフト命令に解釈しなおす訳？
ということは除算命令自体はマクロになるのかな

は？

除算命令に出くわして、せっせとメモリ中のコードを書き換える、けなげな86の姿を想像した・・・

言う事聞かない奴隷なんかいらない

>>412
マイクロプログラムで処理してるんだろ
＞8086のマイクロコードは、命令長が21ビットで、プログラムサイズは504ステップであった

そろそろダンゴさんに〆てもらうか。

うむ

あ

ダゴンを深淵から呼びだしては駄目だ

ん?

は？

は

ビッチ演算

ビット大佐

age

あ

〆

あｇｗ

ぬるぽ

ちょっとスレの趣旨と違うと思うんだけど、適当なところが無かったので、
アドバイス頼む。

アドレスのアライメントをチェックするためにポインタをintにキャストして
&でビットテストしてる。

extern char *p;
if(((int)p & 3) == 0){
//32bit境界にある処理…
}

だけどアドレスをintにキャストするのは64bit時代的に行儀悪いみたい。

でもアドレスをビットテストしたいという状況は普通にあると思うんで、
こういう場合C系的にはどう書くのが上手な作法なの？

>>431
Linux界隈じゃ unsigned long へのキャストが一般的とされてるが
個人的には嫌い

intptr_t / uintptr_t を使えばいいんじゃない？

下位ビットだけ入ればいいので、charでもいい

さすがにそれはありえないだろ?

なぜそう思うの？

バイトオーダー

バイトオーダーは関係ないかと

WindowsならUINT_PTRにキャスト

ダンゴさんがピシっと〆めたな。

うんこうんこうんｋ

う

ん

ち

ゃ

あ

は

た

ぼ

ぬ

る

ぽ

>>450-452
ｶﾞ

http://pc11.2ch.net/test/read.cgi/tech/1142467359/555
これもっと簡単にならないかな？

>>454
--------------------
int my_fputwc(wint_t c, FILE *fp)
{ wint_t r = fputwc(c, fp);
return (r == WEOF) ? EOF : r;
}

int wtbl[0x10000];
void dokkade_jikkou(void ) {
int i;
for (i = 0; i < 0x10000; i++)
wtbl[i] = i;
wtbl[0xffff] = EOF;
}
int my_fputwc(wint_t c, FILE *fp) return wtbl[fputwc(c, fp);]; }

みたいなこと(WEOF(wint_tの0xffff)をEOF(intの-1)に変換)
をもっとスマートに行う方法ないですかね。
---------これで何の不満があるんだ？-----------
wtbl[0xffff] = EOF;
for (i = 0; i < 0xffff; i++)
wtbl[i] = i;
}
--------------------

age

int rotate_0_9(int a){a++;return(a+(((a+6)>>4)+(((a+6)>>4)<<1))<<1)&15;}
or
int rotate_0_9(int a){a++;return(a+((a+6)>>4)*6)&15;}

引数が0～8の時1を加算し、引数が9の時0を返す。

return ++a%9;

% はビット演算じゃないだろう

int rotate_0_9(int a){return a<9?a+1:0;}

DAA

>>457
>>458
>>460
どれが速い？

実測あるのみ

試してみた！
cl /O2 rot9.c
rot9
rotate_0_9_457_1 1873 msec
rotate_0_9_457_2 1272 msec
rotate_0_9_458 4016 msec
rotate_0_9_460 641 msec
>>460が圧倒的だった(俺もそう思ってた)

ソースに続く

>>464のソース (VC6SP4)
----------------------------
#include <windows.h>
#include <stdio.h>
int rotate_0_9_457_1(int a){a++;return(a+(((a+6)>>4)+(((a+6)>>4)<<1))<<1)&15;}
int rotate_0_9_457_2(int a){a++;return(a+((a+6)>>4)*6)&15;}
int rotate_0_9_458(int a){return ++a%9;}
int rotate_0_9_460(int a){return a<9?a+1:0;}
//#define COUNT_TIMES 0x7fffffff
#define COUNT_TIMES 0x7ffffff
#define TEST(func) \
dwTime = GetTickCount(); \
for(i = 0, count = 0; count < COUNT_TIMES ; count++) { \
i=func(i); \
} \
printf( # func " %d msec\n", GetTickCount() - dwTime);
main() {
int i, count;
DWORD dwTime;
SetPriorityClass(GetCurrentProcess(), HIGH_PRIORITY_CLASS);
Sleep(100);
TEST(rotate_0_9_457_1)
Sleep(100);
TEST(rotate_0_9_457_2)
Sleep(100);
TEST(rotate_0_9_458)
Sleep(100);
TEST(rotate_0_9_460)
return 0;
}
----------------------------

printf( # func " %d msec (i:%d)\n", GetTickCount() - dwTime, i);
と変更して計算結果も表示してみたら>>457の最初の式の結果がおかしい事に
気付いたんだけど。

rotate_0_9_457_1 1862 msec (i:0)
rotate_0_9_457_2 1272 msec (i:7)
rotate_0_9_458 3986 msec (i:7)
rotate_0_9_460 671 msec (i:7)

int rotate_0_9_467(int a){
static int t[10]={1,2,3,4,5,6,7,8,9,0};
return t[a];
}
表引き。
これもやってみてくれ。

>>457
やってみるよ。

457_1のiの推移
0 2 6 14 4 10 12 0 2 6 14 4 10 12 0 2 6 14 4 10 12 0 2 6 14
無茶苦茶だった。

rotate_0_9_457_1 1893 msec (i:0)
rotate_0_9_457_2 1272 msec (i:7)
rotate_0_9_458 3996 msec (i:7)
rotate_0_9_460 661 msec (i:7)
rotate_0_9_467 621 msec (i:7)

テーブル引きのがわずかに速いね。
>>460と>>467が微差だったんでカウンタ倍にしてみた。
#define COUNT_TIMES 0xfffffffに変更。

rotate_0_9_457_1 3535 msec (i:2)
rotate_0_9_457_2 2553 msec (i:5)
rotate_0_9_458 7991 msec (i:5)
rotate_0_9_460 1332 msec (i:5)
rotate_0_9_467 1202 msec (i:5)

計ったPCはThinkPad X31 (PenM1.6G Banias) XPSP2

あと>>458は0～8の繰り返しで条件が違うんで
int rotate_0_9_458(int a){return ++a%10;}
に修正してる

_rotate_0_9_457_2 PROC NEAR
; 13 : int rotate_0_9_457_2(int a){a++;return(a+((a+6)>>4)*6)&15;}

mov ecx, DWORD PTR _a$[esp-4]
inc ecx
lea eax, DWORD PTR [ecx+6]
sar eax, 4
lea eax, DWORD PTR [eax+eax*2]
lea eax, DWORD PTR [ecx+eax*2]
and eax, 15
ret 0
_rotate_0_9_457_2 ENDP
掛け算消えるんだね

_rotate_0_9_458 PROC NEAR
; 14 : int rotate_0_9_458(int a){return ++a%10;}
mov eax, DWORD PTR _a$[esp-4]
mov ecx, 10
inc eax
cdq
idiv ecx
mov eax, edx
ret 0
_rotate_0_9_458 ENDP
見るからに遅そうな

_rotate_0_9_460 PROC NEAR
; 15 : int rotate_0_9_460(int a){return a<9?a+1:0;}
mov eax, DWORD PTR _a$[esp-4]
cmp eax, 9
jge SHORT $L53312
inc eax
ret 0
$L53312:
xor eax, eax
ret 0
_rotate_0_9_460 ENDP
普通だね

_rotate_0_9_467 PROC NEAR ; COMDAT
mov eax, DWORD PTR _a$[esp-4]
mov eax, DWORD PTR _?t@?1??rotate_0_9_467@@9@9[eax*4]
ret 0
_rotate_0_9_467 ENDP
短いね
この短さがテーブル参照のオーバーヘッドを相殺してる？
けどaが10以上だったら脂肪

まあ表引きはキャッシュから外れた時にペナルティがあるから
平均的には>460がいいんだろうな。

>>473
確かに、別の環境だと逆転してたり。

#Celeron 430@2.4G XPSP2
rotate_0_9_457_1 1750 msec (i:2)
rotate_0_9_457_2 1359 msec (i:5)
rotate_0_9_458 2969 msec (i:5)
rotate_0_9_460 719 msec (i:5)
rotate_0_9_467 860 msec (i:5)

#Core2Duo 4300@3.2G XPSP2
rotate_0_9_457_1 1281 msec (i:2)
rotate_0_9_457_2 1000 msec (i:5)
rotate_0_9_458 2172 msec (i:5)
rotate_0_9_460 516 msec (i:5)
rotate_0_9_467 656 msec (i:5)

％は割り算があるから遅いってことか。0～9ではなく0～2^n-1の場合にかぎり使えばいいかな。
でも実際の仕事では0～99のローテートでも％で書いたりするなあ。

剰余は定数除算よりも更に遅い。

その剰余をビット演算でなんとか．．．

このスレの355から、剰余をビット演算でする方法が書かれているよ。

入力が必ず0～9なら
a=((a+7)&15)-6; 　// 0～8 が 1～9 9が-6

(aの符号拡張か　4bitの算術右シフト結果)のビット反転と and

ふぬぅ、やっぱ分岐しない上にテーブルも使わない奴は遅いな。

逆に考えて、分岐する上にテーブルも使う奴は・・・


すまん、逆に遅くなりそうだ。

modも内部的には分岐してるだろ。RISCならよくわかる。

え～(*o*) それは２のｎ乗の場合とそうでないので分けてるとか？

剰余　＝　披除数 － (除数 ＊ 商)


一般的には商と剰余は同時に求めることが可能

age

剰余のビット演算への変換ならこのページにあるよ。
http://www.tensyo.com/urame/date/dayTips.htm#MOD

縛りを入れるともっと高速化出来そう…

ある変数の値が

2018か2019
4049か4050
であるか判別する方法は4回比較するしか
ないかな？

愚直な方法だけど比較２回には減らしてみた。
bool check(int value) {
const int mask = ~1;
if( (value & mask) == 2018 || ((value + 1) & mask) == 4050 ) return true;
return false;
}

テストしてないけど。
bool check(int value) {
const int mask = ~1;
if (((abs(value - 3034) + 1) & mask) == 1016) return true;
return false;
}

AND も加算も比較＝減算も、演算量は同じ、ってこと考えたら、どっちも減ってない。
比較４回に比べてリーダビリティは下がってる。

switch (value) {
case 2018: case 2019: case 4049: case 4050:
　　doit();
}

if (v == 2018 || v == 2019 || v == 4049 || v == 4050) return 1;
return 0;
0m48.123s
0m2.250s

const int mask = ~1;
if ((v & mask) == 2018 || ((v + 1) & mask) == 4050) return 1;
return 0;
0m53.281s
0m2.278s

const int mask = ~1;
if (((abs (v - 3034) + 1) & mask) == 1016) return 1;
return 0;
0m52.661s
0m2.167s

switch (v) {
case 2018: case 2019: case 4049: case 4050:
return 1;
}
return 0;
0m46.065s
0m2.087s

if (v < 2018 || (v > 2019 && (unsigned int) (v - 4049) > 1)) return 0;
return 1;
0m45.938s
0m2.086s

いろいろ測ってみた
コンパイラやマシンによって違うと思うけど

４回比較より下の２つのが短いのが不思議ですね。
入力が多数回で、４つの値が均等にバラつくという条件にしたら、最後まで演算しない４回比較
がイイかと思えますが。

>>489
可読性も考慮するの？このスレで？

ちなみに最後の一個はswitchバージョンのアセンブル出力をCに直したもの

iccで試してみた。
# icc -xP -O3 -ip
# icc 10.0
上から、0.3, 0.23, 0.33, 0.3, 0.22[sec/(10000 * 10000call)]だった。
どうやらswitchで書いても一番上と同じような出力になるようだ。
gccでも試してみた。
# gcc -O3 -funroll-loops
# gcc 3.4.6
こちらは、0.16, 0.22, 0.27, 0.17, 0.22[sec/(10000 * 10000call)]だった。
なんでこんなに速いんだ?w

>>495
アセンブリコードで比較してみると分かるんじゃね？

俺には>>486が
if(v==2018||v==2019){
}else if(v==4049||v==4050){
}else{
}
って条件に読めるんだが

俺も俺も

>>486
日本語でおｋ

やっと言う側に回れたか

>>497
いや、今日きちんとみかか村に出撃して
糞仕様について問い詰めてきたけど

case 2018: case 2019: case 4049: case 4050:

で正しい

どうもみんなありがとう

>491
>if (((abs (v - 3034) + 1) & mask) == 1016) return 1;
ここら辺の数値の導き方教えてください
どいった関係で3034とか出すの？ど素人ですんません

>>501
2018+4050=2019+4049=3034+3034

v = [2018 or 2019 or 4049 or 4050] の時
abs(v - 3034) = [1015 or 1016]
abs (v - 3034) + 1 = [1016 or 1017]
mask=0xfffffffeより奇数はそれを超えない偶数に変換される。
(abs (v - 3034) + 1) & mask = 1016

>502
ものっそい感動しました
久しぶりに成長した気がする
この括り方すげー

もはや逆方向にソースから動作仕様を求めることはほぼ不可能だな

かっこいい BIN→BCD は？

速さなら、00h,01h,02h・・・を表に持ち、binで表引き。 <99のチェックは必要。
サイズなら、((bin/16)<<4) | (bin%16) ・・・バイト版。　<99のチェックは必要。
ワードは、／100の商と余りに分けて、上のを呼び、合成。
自分で書いたのはこんな当たり前の奴だなあ・・・

しばらく前はメモリアクセスがからむテーブル参照の方が重いって話だったけど、
また状況変った？

キャッシュの容量
メモリアクセス速度とキャッシュアクセス速度の比率
によって変わるからなあ
細かくいいだすとキャッシュ方式も絡むし
結局「場合による」んじゃねえの

一般論としては、キャッシュに載っている(=頻繁に呼ばれる)ならテーブルの方が速いんじゃないかね。
ただ、この場合の「一般」というのは、分岐が含まれる(=分岐ミスの可能性がある)という前提。

例えば上の((bin/16)<<4) | (bin%16) の場合だと
依存関係が2箇所あって、その部分は同時実行は出来ないけど
キャッシュアクセスに要する数クロック程度の時間と比べてどちらが速いかはわからんね。

テーブルジャンプ(ほぼ同じ値が続く場合以外)は糞だけど。

掛けたり割ったりすることにものすごい抵抗感がある

いや、この場合に限れば、まず間違いなく最適化でシフトやアンドになるよ。

今のチップで乗除算持ってないほうが珍しいよね。俺が書いたのは3MHzの8085だったから、
キャッシュ云々の話はなし。／100だけは除算ルーチン使わないとだめだった。

ARMは現役のチップだけど除算命令なかったような

x/100　は　掛け算があるなら
655*( x + x/2048 + x/16384)/ 65536

その掛け算とｼﾌﾄの計算量なら、100=64hだから、分母の<<2と<<5と<<6を引いたほうが・・・

y = (655*x)>>16 で概算して

while ( x-y*100>=100 ) y++;

ならせいぜいループ１回だろ

最低でもx<6557202(≒(1<<32)/655)が言えなければ。

>>512

(42949672*x+65536)>>32

シフト演算子がアンカーになってしまう（ｗ
>>514-516 は、たぶん数学的には同等なような気がする。

>>518 それ、どういう原理なの？ 32シフトしたら全部なくなっちゃうような気が・・・

32bitレジスタ持ってるような16bit以上のCPUを想定してるんだろ

x386なら32x32bit掛け算の結果が２つのレジスタに判られるから 32bitシフトは上位のレジスタを採用するだけになる。

&gt;&gt;32
>>32

>>512
>>‍32

>>521
>>522
何が言いたいのか意味不明だ。

>>523

これでどうだ

x >> 32

俺他人だけど　>>‍523 色が違うだろって言いたいんじゃないのかな？

>>523
こうすればいいのよ（たぶん）

>>‍527
吊ってくるorz

>>520
あたり。
あと、>>518のxは0～65535の範囲である必要がある。

多少ステップ数がかかるように見えても、まだハードウエア除算は普通の命令２０個分以上に重いからな
1/100 は1/10のルーチンを２度呼んでたな。

1/10は1/2/5 だから１ビットシフトしてから５で割る
65536/5=13107.2 だから13107を係数に使うと誤差は16bitの範囲で１
だけど１ビットシフトしてるから、15bitの範囲になってるから 最大誤差は0.5なんでOK
という事で、最大誤差の0.5を足して

x = x / 2
x = (13107*x+ 6553) / 2^16

を２度繰り返す

>>518 や、>>530 は余りも一緒に求まるの？

この話は掛け算が高速ならという話だから
余りは後から　y=x/N を求めた後 x-N*y で求めればいい

余りだけが必要なら355付近から話題が出てる

実測で、ハードウェアまたはCの除算を上回るルーチン作れるの？うｐして
動かしてみる辛さ

どっかのスレでやってたでしょ。
パソコンの除算命令はレイテンシが大きいから連続して実行させるととても重くなる。
ただ整数ユニットでは実行されないから、その間に他の命令を入れられるならＯＫ


あ、このスレか、>>367-379

int型の除算で標準のものより速いものは作れるのか作れないのか？

分母が固定なら可能。　変数なら無理。　

まてよ。分子が固定な場合、ニュートン法である程度いけるかな・・・・まあ無理か

分母が固定ならif文などで分岐すれば、総合的には速度が上げられるのか?
作ってくれ

経験上、演算や比較文より代入に時間がかかる気がする
たぶんレジスタ動作　+　演算より、メモリ動作は遅いんだろう

>>535
ループの中で定数(変数でも変わらなければＯＫ)で除算するのは、
置き換えた方が高速化できるし、それを実際に使っている。

ピクセル操作のような回数の多いループでは劇的な効果がある。

>>539
それは毎回キャッシュから外れた場合の話。
オンキャッシュなら少しでもＣＰＵを止めない方がいい。

>>538
で、分母はいくらなの？　100の場合はいろいろ出てるよね。

汎用の除算は出来ないか?
例えば2～500まで定数だけ作って分岐させて使う
そのとき高速になるのか?

その分岐の為に時間を使ってしまうから無理だろうね
たとえば関数テーブルで分岐したとしても、キャッシュミスを起こすだろう。

>>542
できる。
それぐらいなら除数の逆数のテーブルを使って可能。分岐はさせないほうがいい。
ただ、16bit全域とかになると、テーブルの方が不利になるCPUが多い。

逆数で気づいたけど、浮動小数点の掛け算で計算すると鈍いの？

逆数の2進展開を持っていたらビット演算できそうだけど・・・どうだろ　速いのか？

たびたび連投すまんが、計算でループを使うなら、はじめに分岐させてもコストは同じようなものだな
2～1024までなら10回の分岐で決定する　10回程度のループを使うなら分岐させた方が良い

>>544
(A*x+B)のＡ，Ｂをテーブルにするの？

でも、たとえば　65535÷３はどうするの？A=21845にしたら、これでは無理だよね

x / n = (Ax + B ) >> C ってどうやって求めるの？

>>548
そうそう。Bは固定でいい。

16ビット範囲の X / Dなら、R = 4294967295 / D として、

X / D の値は (R * X + 65536) >> 32となる。

Dが複数あるなら、D→Rのテーブルを作ればＯＫ

>>550
BCC5.5だけど、上のやつ計算できなかったよ

>>551

__asm{
mov eax, R
mul X
add eax, 010000h
adc edx, 0
mov eax, edx
}

>>550

Rが切り捨てなら汎用になるように
(R * X + R - 1 ) >> 32
でいいんじゃないの？

>>553
65536より、R - 1のがいい理由は何？

理由は、Xが16bitの範囲を超えて入力された時の誤差が多少でも減る事だな

>>555
誤差が許される場合はいいかもね。
そうでない場合は、素直に３２ビットに拡張した方が良くないか？

ようするに
(A * x + A-1 ) >> B
として AのMSBが1になるように B を調整するって事だよね？

Ｂは常に32以上だから、実際には上位ワードだけを>>(B-32) するのだろうけど

>>557
いや、そうじゃなくて、余計なA - 1 という演算を使うのではなく、
550の式を32ビットに拡張すればいいってこと。

32ビット範囲の X / Dなら、R = ((1 << 64) - 1) / D として、
X / D の値は (R * X + (1 << 32)) >> 64となる。

>>530
ルネサスのマニュアルによるとシフト演算と割り算に迷ったら割り算の方が大抵速いみたいなことが書いてあったけど

>>558 さすがに64bit掛算はまだ普及してないだろ

>>559 SHが特殊で固定シフト命令が1,2,4,8みたいな飛び飛びのシフトしか１命令で出来なかったりするからじゃないの？

でも、仕事で使用するとしたら、普通に割り算したほうがソースとして見やすいよね。
2で割るのを1ビットシフトするぐらいはいいけど、あえて複雑な演算にするほど処理能力を求められないでしょ？普通の開発は。

でも、このような議論って技術者としては面白いし、ある意味大切だよね。

>>560
アルゴリズム上の話で、実際に64bit乗算をするわけではないと思う。

元ネタはこれじゃね？
ttp://www.emit.jp/prog/prog_div.html

>>560
コンパイラがやってくれることもしばしば。
まぁ尤も、コンパイラのアセンブリ出力を見たときに「割り算がない」って悩まないためにも
知識はあったほうがいいのだけれどね。

Y = (R * X ) >> 64 って事は 、R = 2^64 / D って事だろ？
Dが16bitの範囲なら Rは　48bitって事になるぞ。　64bitモードに以降しないと効率悪いぞ

もともと
D=100の場合

1　: ( x * 4294967200 + 65536) >> 32
2　: ( x * 4294967200 + 4294967199 >> 32
のどっちが 大きな x までまともに計算出来るかって問題でしょ？

違うか
1　: ( x * 42949672 + 65536 ) >> 32
2　: ( x * 42949672 + 42949671 ) >> 32

BCCで出来ないんだけど・・・CPUのせいかもしれない
内部で32+24ビット程度しか保持していない気がする

>>518がちゃんとうごくぱそこんってあるの?
テストプログラム作ったけど上位1ビットの値は壊れているようだ

#include <iostream>
using namespace std;

main(){
int n;
for(n=50;n<=64;n++)
cout<<n<<" "<<(unsigned int)((1<<n)>>(n-1))<<endl;
}

これっていくつになりますか?
1になるはずですよね?

cout << (unsigned int) ( ((1<<64)-2) >> 63 );

>>570
-1を unsigned にキャストしてるんだからUINT_MAXになると思う。

符号付整数の右シフトが論理シフトになるか算術シフトになるかは処理系定義

>>569
unsigned __int64かunsigned long longでおｋ

>>570
なんで普通のコンピュータで使えるビット数越えたシフト使うんだ。
1 << 64なんてオーバーフローで0になること確定じゃないか。

~0ULLでおｋ

>>569

>>563のコードと同じだからそっちでやってみればいいんじゃないか。

#include <iostream>
using namespace std;

main(){
unsigned int n;
for(n=60;n<64;n++)
cout<<n<<" "<<(unsigned int)(((1<<n)-2)>>(n-1))<<endl;
cout<<63<<" "<<(unsigned int) ( ((1<<63)-2) >> 62 );
}

63の値が変わるのはなぜ?

>>577
サイズを超えるシフトは未定義。

ARMは割り算使うと糞遅いから困るな。

age

32bitパソコンだと、16*16しか値は保証されないよね
a + b * 65536　などと表示して、32bit以上を表現したら
ハードウェア搭載の除算よりビット演算のほうが速い?
除算が現れたらintを16bit数に変換して計算する

X = 65536 、R = 1/Xとすると

(a+bX) / (c+dX) = (b+aR) / (d+cR)であり、

1/(1+R)　のテイラー展開は、　1　-　R + R^2 - ・・・+(-R)^n+ ・・・
Rの巾は非常に小さいため2乗までを採用すると、

(a+bX) / (c+dX)　=　( (b+aR)/d ) * 1/(1 + cR/d)
=( (b+aR)/d ) * (1 - cR/d + (cR/d)^2 )
=1/(X^3 * d^3) * (a + bX ) * (c^2 -cdX + d^2X^2 )　となる

これで32bit除法を高速化出来るか?

32bit内で処理しようとすると大変だ　普通にCPUに任せた方が楽そう

BOOL bResultの値が 0 か -1
if (bResult == 0 || bResult == -1)

じゃなくて、一発で調べる方法はないですか？

BOOLなのに何故数値と比較してるんだ？

GetMessageじゃね？

BOOLは偽==0、真==0以外じゃなかったか？
定義を調べた方が良さそう。

世の中には変な使い方する椰子がいるのよ。MSとかw

ttp://msdn.microsoft.com/library/ja/default.asp?url=/library/ja/jpwinui/html/_win32_getmessage.asp

if(bResult^0==-1)

x^0=x

if (((((uint32_t)bResult) + 1) >> 1) == 0)

同じ3演算だけど-1をロードしないだけ早いかも？
uint32_tがいいかどうかはよくわからない。

-1か0、限定なんだからそのまま書いたほうが分かりやすいような。

>>588
( ･д⊂ヽ゛

>>588
>警告 GetMessage 関数は、0 以外の値、0、-1 のいずれかを返します。したがって、次のようなコードは避けてください。



そもそも…

まー継ぎ接ぎだからな

>>591
右シフト・条件分岐より、比較・条件分岐の方が速くない？

if (((uint32_t)bResult + 1) <= 1)

>>596
マシン語レベルでは結局0比較に変換されるから同じ程度じゃないかな。
でもCレベルではそっちの方が短くていいと思う。

>>597
ちょっと前まで主流だった某CPUではシフトは加減算の
8倍遅かったし、それ以外のCPUでも演算器の関係で
シフトの方が並列化されにくいかも、とかそういう話。

で、何億回呼ぶのよ

シフトのほうが速いと思ってたのに・・・

>>599
そんなこと言うならこのスレの意義って一体なんなのさ。

確かにWindows APIをそんなアホみたいに呼ぶ事はないだろうが、
こんな風に一般化してみれば、それなりに使い道はあるだろ。

_Bool bounds_check(int n, int lower, int upper)
{
　return (unsigned)(n - lower) < (unsigned)(upper - lower);
}

>>600
加減算よりシフトの方が速いCPUなんてあるのかな？
演算の頻度からいっても普通は加減算を最速に設計すると思うけど。
x86系を数種類しか触った事ないから、他にはあるのかも知れないが。

ハードウェアの構造上加減算よりシフトの方が圧倒的に単純なんだよ
小さい加算器を作ったことがあればわかるはず
クロック数が一緒ってことはあるかもしれんが、
シフトの方が遅いってことはまずないだろう

ARMだと全命令にプレディケーション使えるからCレベルの単純な分岐は直列化できるよ
分岐は極端に遅いなんていうのはCellプログラマだけにしてください。

>>602
このケースは1bitだからその通りだけど
x86の8086-286までは、2bit以上のシフトは遅かったんだよ。
最初は直接bit数指定のインストラクションすらなかったし。

ttp://answers.google.com/answers/threadview?id=388350

>>603
単純な分岐なら、if文使ってコンパイラに任せた方が速いね。
絶対値求める時とか、NULLならreturnするとか、分岐コストかからなくていい。

むしろif文にbool型しかとらないJava/C#が異端なんじゃねーの？
俺もbool型オンリーの方が好きだが、スクリプト言語してるとそうじゃない方が多い気がする。

ifの選択肢にTrueとFalse以外なんてあり得るの？

if(666){//実行されます。}

コメントに括弧閉じ書いて意味あんの

if (GetMessage(...) <= 0)

で充分でね?

>>602
シフタってのはデータセレクタの塊だから多ビットのシフトは
シリコンの面積を喰うのよ

>>611
-1以外の負の値が未定義

シフタのないプロセッサには出会ったことが無いけどね。

if (bResult == 0 || bResult == -1)

は

if (((uint32_t)bResult + 1) <= 1)

と同じコードになったぞ。
gcc賢いな。
ちなにみRISCでどうなるか見たかったので団子の嫌いなCELLのgccでコンパイルしたw
ちなみにCELL(SPE)もヒントブランチあるから。
むしろARMのプリディケーションいまいちだと思うけど。

知ってるが

Cellのスカラ性能が
気に食わない

分岐ヒントもBranchの15クロックくらい前くらいに入れないと駄目じゃなかったっけ
しかも二重に使うとハングする致命的なバグ持ちだから始末に困る

if (bResult == 0 || bResult == -1) こんなん対して食わないだろ゜

SSE4.1のXMMに対する比較命令が加わったから4条件同時判定とかも便利そうだね

ダンゴさんが連投するとスレが引き締まるな

ダンゴage

test

test

http://www.nicovideo.jp/watch/sm1779811

年末あげ

ttp://itl.jisakuita.net/core2_mossari/1162381694.html

ダンゴさんすげえな

sge

V(･∀･)V

あげ

以下の2つの値があったとします。
x1 = 0xFF842144
x2 = 0x5400FF33

ユーザからの入力u1、u2が入力された場合
考えられるケースは以下の4つになると思います。
・u1=x1、u2=x2一致
・u1=x1一致
・u2=x2一致
・どちらとも一致しない

最低3回比較しないとどのケースか判断できないって
思い込んでるのですが
何かいいアイディアくれる人いませんか？

愚問だと思いますが。。

しかし、そんあ80年代前半のBASICの論理式みたいなアナクロな発想をするって
今日日奇特な人だね。

u1がx1と一致するケースに
・u1=x1一致、u2=x2一致
・u1=x1一致、u2=x2不一致
がある
u1がx1と一致しないケースに
・u1=x1不一致、u2=x2一致
・u1=x1不一致、u2=x2不一致
がある

つまり４通り
比較は最大２回

その比較を10^12回通りくらい計算するつもりなら最適化もあり

あらかじめ
p = x1 XOR x2
の値を取得しておく
q1 = p XOR u1
q2 = p XOR u2
を得る

SSE4のptest使えば一回で済む

>>634
得た後はどうすればいいのw？
q1とq2をどうやって使うの？

>>632
＞・u1=x1一致、u2=x2一致
あんた馬鹿?

>>635
無理だろ，あれは and と andnot だから．pcmpeqd の方が良さげ

632ってこういうことだろ？

if( u1 == x1 ) {
if( u2 == x2 ) {
//ryouhou
} else {
//u1 nomi
}
} else {// not
if( u2 == x2 ) {
//u2 nomi
} else {
//ryouhou itti sinai
}
}

どこも間違ってるように思えないんだが。

しかし、BY（文脈読めない）な奴が多いな。

ここがどういうスレかを考えれば、>>630が何を聞きたいか
多少説明不足でもだいたい分かるだろ普通w

ほうほう。それでそれで?

int a[] = {両方一致, 片方一致, 片方一致, 一致しない};
b1 = (u1 == x1)
b2 = (u2 == x2)
return a[(b1 << 1) | b2];

× int a[] = {両方一致, 片方一致, 片方一致, 一致しない};
○ int a[] = {一致しない, 片方一致, 片方一致, 両方一致};

ゼロフラグでレジスタに0,1をセットする命令があるならソレが効率的だね。

それがないと、減算して、さらに１引いてキャリーを出してローテートしなくちゃいけない
アキュムレータが2個しかないCPUなら
AccA := u1-x1-1;
RotWithC(AccB);
AccA := AccA+x1+1-x2-1;
RotWithC(AccB);
AccB := AccB and 3;

結局、そのあたり何が効率的かはアセンブラで見ないといけないけど
アセンブラで出来る高速化は、リニアにしか効かないから、そんなに意味ないんだよね

全面的に同意．ただ２倍位速くなることもあるから最後の手としては有効．まぁ今は可能 intrinsic 使うけど．

割り算を掛け算とビットシフトに置き換える計算式求めるプログラムできた

#include <iostream>
using namespace std;
main(){
unsigned int N,n,k;
for(N=2; N<65000 ; N++){
for(n=0; (1<<n)<N ; n++); n+=15;
double X=(pow(2,n)/N);
unsigned int Y=(unsigned int)X;
unsigned int d=0;
if(X-Y<=Y+1-X)d=(unsigned int)(pow(2,n)- (N-1)*Y)-1; else Y++;
printf("x /%5d = ( x * %5d + %5d ) >> %2d",N,Y,d,n);
for(k=1; k<(1<<16) ; k++) if(k/N != ((k*Y+d)>>n))break;
if(k==(1<<16))printf(" OK\n"); else printf(" ERR\n");
}}

64bit機か、内部で64bitまで計算結果を保持しているなら
32bitの割り算も出来るけど646は16bit同士です

GCC の中見りゃあるんじゃね？

>>648
gcc のカオス・スパゲッティ状態を知らぬようだな。

勧めるならせめて Small-C くらいにしとけ。
このルーチンなら 工学社から出ていた
Small-C ハンドブックにもちゃんと説明されていたんだし。

ハッカーの楽しみ買ってきました～
これから読みますﾉｼ

Hacker's Delight やっと届いた

俺もアレ訳本出る前ネットショップで買ったわ

a

a

a << 1

a

あげ

あげ

あげ

なにこのスレきもい。
でも懐かしい。

　　　　|
　　　　|
　　　／￣￣￣￣￣￣
　 ＜⌒／ヽ-、_＿_
／＜_/＿＿＿＿／

ダンゴさんを称えるスレというわけではありませんが、まあ、KY。

GCAの作者のページにビット演算が載ってたけど今いちわからん

ViViの作者のページにもビット演算が載ってたけどだいたい理解した
http://vivi.dyndns.org/W/254

>配列による状態表現よりも処理が高速になる場合が多い
この表現は凶悪だな。何故なら、高速にならなかった場合にはかなり遅くなる可能性があるからだ。

age

age

燃料がないな

16bitカラーで　5：5：5 とか 5：6：5 とか　の時代なら色々やったけどな

AltiVecにも16bitカラー用の演算があったな

こちらのスレから誘導されて参りました。よろしくお願いします。

スレ立てるまでもない質問はここで 第91刷
http://pc11.2ch.net/test/read.cgi/tech/1209716212/171

以下の条件で、32bit値のハミングウェイトが素数か否かを判定する
出来るだけ高速な方法を探しています

・入力はランダム
・（最悪ではなく）平均速度が速いことが望ましい
・0、1は素数ではない（偽になって欲しい）
・ハミングウェイトそのものの値は必要ない
・64bit拡張などは必要ない。32bit決め打ちで良い
・外部メモリはあまり使いたくない

皆様のお知恵を貸していただけませんでしょうか

一応、今はこんな感じです
ベタな実装で恥ずかしいですが…

int hw_is_prime(unsigned long x)
{
　　x = ( (x & 0xAAAAAAAA) >> 1 ) + (x & 0x55555555) ;
　　x = ( (x & 0xCCCCCCCC) >> 2 ) + (x & 0x33333333) ;
　　x = ( (x & 0xF0F0F0F0) >> 4 ) + (x & 0x0F0F0F0F) ;
　　x = ( (x & 0xFF00FF00) >> 8 ) + (x & 0x00FF00FF) ;
　　x = ( (x & 0xFFFF0000) >> 16) + (x & 0x0000FFFF) ;

　　return (1 << x) & 0xA08A28AC;
}

1 << 32 の結果って決まってたっけ

処理系定義かな。0ビットシフトになる場合と32ビットシフトになる場合が一般的だと思う。

まぁ 8bit, 16bit, 32bit が int の場合と、
64bit が int の場合では結果は明らかに異なるよな

8bitがintになることってありえるっけ

規格は一応-32767～32767だからないんじゃね？

1ビットマシンとか4ビットマシンとかってCでプログラミング可能なの？

CHAR_BIT >= 8 だけど、
別に変数１つをレジスタ１つで扱えないといけないわけじゃないし
問題ないんじゃね？

ダンゴさんのカキコでスレが加熱したな

レス番飛んでるな

ダとかンとかゴとか入ると飛ぶんだよな。

実は見えてる

ダンゴって名前を嫌がるのは、
体型が肉団子だからだよな。

だんごはこれだろ

━━━━━━┓がどうみたらだんごに見えるねん

あたまわるいんとちゃうか

虫除けのようなものだよ

ダンゴさんってどんな仕事してるの?

名無しさんの書き込みでスレがヒートアップしたな。

他愛もない雑談だけどな。
と、だけ書くのもなんだから、ちょこっとマジレス。

ANSI C での int の定義は処理系依存で、CPUのレジスタ幅によるらしい。
なので、Z80 なら 8bit の筈だけど、
大体のZ80 C処理系では char=8bit, int=16bit と扱う。
なんで int は 16bit より大きいという誤解があるんだろうなぁ。
その昔は char=7bit なんで処理系もあったというので、
油断は出来ないように思うんだよ。

INT_MINは-32767以下、INT_MAXは+32767以上じゃないといけないと決まってる
昔の話は知らん

1ビットCPUは実際にあった
http://www.d1.dion.ne.jp/~ytera/1bitcpu.htm

昔はやりたい放題だったかも知れないが、
今は規格に準拠した処理系であれば int >= 16 bits なのは真理。
あと、int のサイズの定義は CPU のレジスタ幅にして欲しそうな定義ではあるけど、
そう断言している訳じゃない。
実際最近でも 64-bit マシンで int = 32-bit のことがある。

>>689
＞その昔は char=7bit なんで処理系もあったというので、
無い。

ごめん、間違い。

uartと間違えたんだな

ハネウェルの昔のマシンとかは 6bit 単位のマシンとかがあったから、
それとの勘違いだろ。(7bit があったかどうかは知らん。)

まあ単位が 6bit なのは uart と同じ理由だが。

>>691
それはCPUと言うよりリレーの置き換えみたいなもの
Connection Machineのはまともな1bit CPUだけどbit sliceだから何bitにでも
化ける

あげ

11100111

こんなビットがあったとき、0が4と5ビット目に
存在するってどうやって調べるのが効率いいのかな？

個数はわかるけど位置はどうすりゃいいんだろう

Hacker's Delight 嫁

>>699
11100111 and 00011000

8bitなら256個のﾃｰﾌﾞﾙ持てば最速じゃね？　16bit以上なら、シフトして端のbitの0/1と
シフト回数で判別。

>>699
ループ

>>703
>>701

aビット目とbビット目が動的に変わるなら、マスク作ってandとった方が良いかもしれない。

>>699
問題文は正確に

>>699
４、５ビット目というのは変わりうるのよね？
あと個数が２個というのも変わりうるのよね？

>>699
ああ、あと、いつもがそんな風に左右対称とは限らないのよね？

一番下の0のビットだけを１にするのなら

y := ( not x ) and ( x +1)

で出来るから、ビットが1の個数が判る命令BitCount があるんなら
BitCount( y-1 ) で求まるよ

で x:= x or y; として一番下の0だったビットを1にしてから $FF になるまで繰り返せばいい

>>708
それって並列にできないですかね
無理ですよね.....

bit演算で128、64、32bitを扱う場合
みんなどんなふうに宣言しますか？
C/C++でのバターな方法が解りません

まずトラを数匹用意します。

あるプログラムで実際にあったコード。
普通ループではカウンタを＋＋していくと思うけど、
（iを1,2,3・・・と加算）
一回処理するごとに左に1ビットシフトしていた。
（iを1,2,4,8・・・とシフト）


普通こういうコード書きます？仕事で。

>>712
1989年ぐらいに見た記憶があるｗ

グレイコードを扱うような貧弱なCPUに対するコードなら在り得る。

１ビットずつスキャンしていく場合には使う。

>>712
普通にあるし、速度面だけでなく、その方が可読性があるものもある。

終了条件でいつも悩むんだけどね。

for( bit=1 ; bit ; bit<<=1 ) cnt += ( ( data & bit) >0 );

こういうの？

アセンブラで１～８回のループをシフト+キャリーでやることはあったな。

もしかしたらループ回数が３２かいを超えたら・・・
どうするの？

>>720
普通にカウントしろよｗ

正直別にどうでもいい
泣くしかない

0xC89664
の１バイト目・２バイト目の値を求める方法をお願いします。

>>723
貴方の小人は頭から食べるのですか？　お尻から食べるのですか？
http://www.aozora.gr.jp/cards/000912/files/4673_9768.html

囲碁（9路盤）のbitboardを作ろうとしています。
9x9なのでSSE2使えば128ビットレジスタ一個に収まるのでかなりの高速化が出来ると思っています。

囲碁のルールに上下左右を全て囲まれた石の塊は盤から取り除かれるというのがありますが、
これを高速に行うにはどうしたらよいでしょうか。

問題はSSE2は128ビットを一塊としたシフトが行えないことで、これのせいでどうしたらよいかわからなくなっています。
よろしくお願いします。

モンテカルロ木の実験ですか?

>>726
そうです。
モンテカルロはスピード命らしいので、SSEを使えないかと思っています。

左シフトなら paddq である程度代用出来るだろ

paddqって64ビットの境目で切れ目が出来てしまいませんか。

128ビット丸々だとバイト単位の命令しかないからねぇ。
x64環境を使っていいのならビット単位をやめてバイト単位にして
16本のXMMレジスタを9本使って9x9にした方がいいんじゃないかな？

それならビット単位でshort[9]でもよさそうですが、
バイト単位にしたほうが有利なんですか？

ビット単位で操作できないから困ってたんじゃなかったの？

レジスタを9本も使うなら32ビットのレジスタでも9x9の盤は収まってしまいます。
その場合、ビット単位の操作は可能です。

x64でレジスタが16本あったとしても通常のレジスタを9本も占めるというのは考えにくいですが、
ＸＭＭレジスタなら9本使っても支障ないということでしょうか？

>>729
最大9bitしかシフトしないでしょ？　なら　境界にデータを置かなければいいでしょ

あるいは16bitを１列にしてレジスタ２つにしたらどう？

>>733
x64で汎用レジスタが増えたとはいえ9本も使えばループや分岐に支障が出ると思うよ。
その点XMMレジスタなら浮動小数点演算しなければ基本的に空いてる。

725です。

すいません。
皆さんにレスしていただいておいて申し訳ないのですが、
高速化について調べていたらGPGPUというのが見つかりました。

グラボに計算をさせるというものなのですが、上手くツボにはまれば
CPUの何十倍もの速度がでるそうです。

囲碁がはたしてグラボに計算させるのに向いてるのかどうかわかりませんが、
SSEは一旦忘れて、GPGPUについて調べてみようと思います。
グラボも３～４万だせば結構いいのが買えるみたいです。

とりあえずGPGPUスレとCUDAスレにいって雰囲気つかんできます。

皆さんのレスには感謝しています。
失礼しました。

そっち行ってもいいならFPGAっていうテもあるかもしれん。

5年ほど前にFPGAでオセロの石を返す部分を作ったが
普通にCPUで計算するより遅かった

>>736
CUDAするなら前もって、GPUに計算させたい部分
設計しておけ
わしは今日から3日でモンテカルロをCUDAで解けるように
勉強する

>>739
どもです。

ところで最新ハイエンドGPUはピーク性能1TFLOPS超えるらしいですね。
ＨＤＤもテラバイトの物が出てるし、時代はもうテラなんですねぇ。

>>740
Radeon HD3870とGeforce9800GTXもってるけど
両方とも労せず2000スレッド以上生成して並列に計算できるよ

>>725
一命令ではできないが，シフトしたいビット数を n として n/8 と n%8
とに分けてシフト命令使って後で合成すれば可能

>>738
enumの様に贅沢にintを丸々一つ石に配分した方が良かったかもしれないね。

ベクトル演算を利用するなら　閉曲線の内側か外側の判定で巻付判定法を応用するといいように思うな

ビット演算じゃないけど

あげ

う

今どきビット演算で高速化とかｗ

プログラミングマニュアル1・基本仕様ガイド
の
・式

ってとこに詳しく書いてるだろ...読みもしないで不思議とか言うな

誤爆すいません

こやつめ!

2^a　を渡されたときaを求める方法で何かいい物はありませんか？
なるべくループやlogを使わない物がいいです

>>751
追記、1≦a≦9

>>752
自分の名前間違えた>>750じゃなくて>>751

５１３個の配列持って、その中に１～９を入れておく。[1]=なし、[2]=1、[3]=なし、[4]=2、・・・
[512]=9　演算はこれが最速。

サイズが問題なら、
if( n & 0x200 ) return 9;
if( n & 0x100 ) return 8;
・・・
if( n & 0x002 ) return 1;

x86ならBSF

char bit[256] = {1,2,0,3,0,0,0,4, 略 };

bsf(int n) {
int r;
if ((r = bit[n&255])) return r;
n >>= 8;
if ((r = bit[n&255])) return r + 8;
n >>= 8;
if ((r = bit[n&255])) return r + 16;
n >>= 8;
if ((r = bit[n&255])) return r + 24;
return 0; //解なし
}

こんなのどうよ?
bsf(bits){
bits-=1;
int num;
num = (bits >> 1) & 03333333333;
num = bits - num - ((num >> 1) & 03333333333);
num = ((num + (num >> 3)) & 0707070707) % 077;
return num;
}

>>754-758
ありがとうございます。みんなカッコイイ

>>757は
char bit[256] = { 0,1,2,0,3,0,0,0, 4,0,0,0,0,0,0,0, 略 };
の間違いだった。
んで結果を-1すれば合うんじゃないかな。

こんなんでどよ
int f(unsigned n){
    int a=1;
    unsigned b;
    n>>=2;
    b = n>>4;if(b)a+=4,n=b;
    b = n>>2;if(b)a+=2,n=b;
    return a+n;
}

"_\0\5\1\10\6\2__\4\7_\3"[n*0xCA030FF>>28];

お前頭いいなー、でも
"_\1\6\2\011\7\3__\5\010_\4"
じゃないか

もう少し小さいハッシュもあった
"\1\2\3\010\6\4\011__\7\5"[n*0x5300000>>28];

あー間違えてたーthx
そしてそっちのハッシュのほうが優れているね。

なるほど、ハッシュってそういう使い方するんだ。

>>762-763
異次元過ぎてついて行けないのだが解説頼む

俺もわかってないが
gperfとかで完全ハッシュ関数を作るのと同じように
(文字列ではなく)特定の数字から対応する特定の数値への完全ハッシュ関数を作っているんだと思う。
どうやって導いたかなんて知らん。

へええ
左シフトしたときに
あるビット範囲（この例だと28ビット目から31ビット目）が
シフト回数ごとにバラけるようにしているのか

シフト回数　　(n*0x5300000)のbit28～31の値
　　1　　　　　　　　0
　　2　　　　　　　　1
　　3　　　　　　　　2
　　4　　　　　　　　5
　　5　　　　　　　　10
　　6　　　　　　　　4
　　7　　　　　　　　9
　　8　　　　　　　　3
　　9　　　　　　　　6

んで配列テーブルをlookupすると。

完全ハッシュ関数って、元が異なれば必ず先が異なる関数のことだっけ。
じゃないとこれ使えないよな。

小さいというのは先の範囲、つまり今回は28～31の４ビットのことか。
確かに小さいほうがメモリとキャッシュに優しいですな。

という感じであってますか。

>どうやって導いたかなんて知らん。

俺も知りたい。

頭良すぎる

2chってすげーな

ビット演算ってたしかにすごいけど、
ソースに組み込むときは、その演算の意味とメリットなど
ビット演算を導入した経緯や思想も書いてほしい・・・

ソース理解に時間がかかったり、修正が大変・・・
まあ、俺がお馬鹿なのかもしれないけど。

あと、763って751からの流れなんですか？
それとも別の流れ？

最後の2行から見ても明らかに

>まあ、俺がお馬鹿なのかもしれないけど。

が正解。

このスレって頭のいい奴もいるけど、
771みたいなバカもいる。
バカはROMっていろ！死ね771！！

まあ、バカにレスする奴はもっとバカだけどな。

1、2、4、8、16、32、64、128、256、512の完全最小ハッシュ値を作る。
ttp://www.ic-net.or.jp/home/takaken/nt/slide/hash.html
これか？
>>762は本当に頭がいい。>>763の書き込みがなかったら
意味も解らずスルーするところだった。

512の完全ハッシュを作ってそれを1～9のテーブルに掛けるって事？
分かった気がする。

>>775
でも、保守する奴が >>762 みたいに頭いいとは限らんから、
仕事のプログラムなら >>754-755 あたりのほうがいいと思う。

当たり前。こんなのは所詮パズル。商用コードでこんなの書けない。
>>762みたいなのが許されるのは趣味のプログラミングだけだよ。

後は極端に処理速度がネックになってるところとか、
ビックリするほど容量が無いプラットフォームとか、
コンパイラが準備されてなくてアセンブラで書かなきゃいけないような場合、
更にRISCみたいに見た目と実行順が違うような環境だと
読む量が少ない短いコードが逆に役に立つ。
自慢を理由に書くと間違いなく死を招く。

コメントで書いておけば十分じゃないかな。
今でもまだまだ、速度やサイズ重視の分野はあるし。だいぶ少なくはなっているけど。

現状、用途として大きそうなのはシェーダー周りか。

画像処理ならいくらでも速度欲しいけどな

昔、VUアセンブラの実装をしたが、ライブラリの増加により俺の約700byteのプログラムが
入らなくなり削りに削って「400byteだけ下さい！」と上司に嘆願したのは懐かしい思い出。

>>777
それは同意だけど、 >>762 のエッセンスを抜き出して、わかりやすくすれば
いいんじゃないかな

おそらく、2^a を掛けると aビット左シフトする、というのは誰にも自明だけど
１～９の値にマップするマジック定数がややトリッキーかと

なら、見た目にわかりやすいようシフト数を４倍にして、（ついでに右シフトにして）
こんな感じでどうだろうかね(64ビット整数が使えることが前提だけど＾＾）

/* assume that n is 2^a (1<=a<=9) */
　return (0x9876543210LL / ( n * n * n * n )) & 0xf;

一番右の1を探すとき~a&(a-1)でできますよね、じゃあ一番左の1を探すときは何かありませんか?

掛け算が４回・割り算が１回ってのが、演算量的に・・・　俺が8bitに慣れてるからかな？
64bit整数があるにしても、nが32bitならn*nで64bitでしょ。中間結果でbitが失われるんじゃ？

>>785 754とか755じゃダメなの？もっと速い／小さいのってこと？

>>785
関係ないがa&(-a)で右端の一ビットを得られるぞ、左端は無理じゃないか

http://www.nminoru.jp/~nminoru/programming/bitcount.html

>>787-789
どうもです、今見た資料に左端を操作する命令列は存在しないって書いてあったorz

左右反転するビット演算子でもあればね

a = ( ( a >> 16 ) & 0x0000ffff ) | ( ( a << 16 ) & 0xffff0000 );
a = ( ( a >> 8 ) & 0x00ff00ff ) | ( ( a << 8 ) & 0xff00ff00 );
a = ( ( a >> 4 ) & 0x0f0f0f0f ) | ( ( a << 4 ) & 0xf0f0f0f0 );
a = ( ( a >> 2 ) & 0x33333333 ) | ( ( a << 2 ) & 0xCCCCCCCC );
a = ( ( a >> 1 ) & 0x55555555 ) | ( ( a << 1 ) & 0xAAAAAAAA );

>>786
もちろん変数n は64ビット長
LP64なら long型だと思ってもらえばいいです

演算量については、いまどきの投機実行するCPUなら
下手に条件判定入るよりは速いと思うけど、・・・まあ状況次第ですね

ｎが64bitでも、n*n*n*n の中間結果はbit失われるでそ。

でも、仕事に使うとなると、
「シンプルにしようや」
で終わってしまうんですよね～
そうすると、754や755に落ち着くのかな・・・

そりゃそうだよ。

よほど特段の理由が無い限り、シンプルが一番。

裸が一番いいのと一緒だ

>>794
2^9まででしょ？

は？

0x1 * 0x1 => 1
0x3 * 0x3 => 9
0x7 * 0x7 => 0x31
0xf * 0xf => 0xe1
0xff * 0xff => 0xfe01
0xfff * 0xfff => 0xffe001
0xffff * 0xffff => 0xfffe0001
0xfffff * 0xfffff => 0xffffe00001

これに規則性みたいなものを感じるんですが、
何か法則があるんでしょうか？

初めの3つはともかく、
9*9=81
99*99=9801
999*999=998001
と同じようなもんだろ

よくわからんが、ビット演算とかって、日本人よりも
インド人のほうが面白い発想しそうだね

>>800-801
２進数に考えれば、最初から綺麗に並ぶよ。

1 * 1 = 1
11 * 11 = 1001
111 * 111 = 11001
1111 * 1111 = 11100001
11111 * 1111 = 1111000001

0xffff * 0x10000 => 0xffff0000
0xffff0000 - 0xffff => 0xfffe0001
特に面白い事実はなさそうだが

99*99=9801
これが国民機ナンバーの正体かー
すると8801は？
93.8136 * 93.8136 = 8800.99
収束しないのか

収束？

ごめん適当言った

無理数ね。

λ... PC-8001, PC8201, PC-6001, &c. ...

獣の数字にまつわる屁理屈と同じようなもんだな
あえて8801に意味を見出すなら99*99-1100とかなんとか

9801-1100 = 8701だな
俺頭大丈夫ｋ

PC9801が長いこと繁栄したのは99*99=9801
こういった力(ちから)を持つ数字が隠されていた影響に違いない。
その証拠に型番が9821に変わろうとしたとたん没落した。
きっと9801のままなら永遠の存在だったんだよ。

>>798 そうか、9bitのハッシュのエレガントな解法だったのね。ごめん。
ハッシュって、必要の都度、bit数見極めて作らなきゃいけないんだな・・・

実際に仕事でも使用可能な、
1.実用性がある
2.比較的わかりやすい
ビット演算のアルゴリズムって何だろうね・・・

名前がつくぐらい有名になればいいんじゃないかな。
例えばコメントに
// 762氏ハッシュ
とか書けるぐらいに。

すみません、
＞"\1\2\3\010\6\4\011__\7\5"[n*0x5300000>>28];
の頭の"\1\2\3\010\6\4\011__\7\5"がいまいち良くわかりません。

ただの文字列リテラルだよ

コメントに、「ハッシュがどうの」なんて書く奴ばっかだからダメなんだよ。
コメントに絶対に書かなきゃいけないのは、>>751-752だよ。
どういう実装をしたかのコメントなんて二の次三の次。

それなのに仕様のコメントを怠ったままで「すげーテクニック使ってるんだぜ」的なコメントを残しても意味なし。
そんなものを残すぐらいなら、(最低限の>>751-752の他に)assertでも使った範囲チェック入れとけ。

もちろん、>>762のやり方に対するコメント(完全ハッシュ関数とテーブル)はあった方が良い。
けど、仕様についてのコメントの方がはるかに重要。

日本語でおｋ

日本人でおｋ

二本イレマスカ？

イマレス

#if 0 // オリジナルのロジック
...;
#else // 速度重視で書き換え
...;
#endif

"..."[...]という書き方をこの流れで始めて知った

何でこのスレにいるかって？
知るために見ているのさ

K&Rの頃のCをやってた人間からすれば常識

>>816 文字リテラル "abc"とかならキャラ型の配列だって判るでしょ。
スペース（0x20）より小さい値のcharは 「\８進数」 で書く約束になってる。
"\1\2\3・・・"は、char xxx[ ]={ 1, 2, 3, ・・・, 0 };という配列が生成される。

>>826
＞スペース（0x20）より小さい値のcharは 「\８進数」 で書く約束になってる。
なってない。

\001 \002 \017 とかだよ。　Hexの場合は \xhh と書く約束になってる。
俺のはLSIC85とか adUc51とか、クミコ系ばっかりで、ANSIは知らないけど。

0x20以上の値で使ってはいけないという決まりもないわけで。

最下位8bitについてなら左右を逆転するコードあった筈
こんな感じだったと思うけど、よく覚えてないや

x:src y:dest
s=(x*0x02020202)&0x84422010
t=(x<<3)&0x420
y=(s+t)%1023

>>792で既出だべ。

>>828
\n \t \r とかもあるわけで。

>>832
は？

文字リテラルが配列の名前？？？
どうも「文字リテラル＋[]」が良くわからん。
ビット演算うんぬんではなく・・・
C言語でこれを書いてコンパイルが通るのか？

どうもこのスレに付き合うには、大学などできちんと学ぶか
元々、この手のことが好きじゃないとついていけませんね・・・

社会人になってから、プログラムを覚えたアホアホな俺の
プリンみたいな脳みそでは、だめかorz

なんでワカラン？？？　大学とか関係ないぞ。

char * buf = "01234567";
char a = buf[0];

が判れば、

char a = "01234567"[0];

だって判るだろ。

char a = 0["01234567"];

こんなのもある。これが直感的に納得しづらいというのはワカランでもないけど、

char a = "01234567"[0];

こっちは普通だべ。

>>834
>元々、この手のことが好きじゃないとついていけませんね・・・
当たり前だと思うんだが。

文字列定数がメモリ空間に配置されている状態をイメージできていないんだな。
プロセスメモリエディタかバイナリエディタと睨めっこでもしてみればいいんじゃね。

文字列リテラルは、コンパイラがDATAやTEXTのようなセグメントに配置して
プログラムの中に埋め込まれるちょっと特殊なchar[]にすぎん。
"hoge"とか書いた場合、これはそういう配列を暗黙にどっかに確保しろよと
コンパイラに言っているのと同時に、式の中で評価されるときは、その（無名の）
char配列の名前と同等に扱われる。

要はchar[]なのだから、char*な変数に文字列リテラルを代入したり
printf()のような関数に文字列リテラルを引数として渡したり、ということは
普通に・当然のようにやっているはずだ。
さすがにprintf("hello, world"); というコードを見たことが無いとは言わせない。

ならば、[]演算子を適用できるということも当然分かるはずだな。
多分、そういうコードを今まで見たことが無い、見慣れない、ってだけだろう。

>>834
[]を特殊なものだと思うからいけない。ただの演算子だ。
a[b]とあったら必ず*(a+b)と置き換えが可能だから、ただのポインタ演算とデリファレンスに成り下がるだろ。
デリファレンスするために、aかbのどちらかはポインタでもう一方は整数でないといけないだけだ。

例えばchar a = 0["01234567"]とあったらchar a = *(0 + "01234567")になり、即ちchar a = *("01234567")であり、char a = "01234567"[0]だ。
これでも理解しにくかったら、全部一時変数にしてしまえばいい。
const char * p = "01234567"; int i = 0; として、char a = p[i]; ならわかるだろ。。

おそらくは、
　配列の名前[インデックス]
のように教えてる参考書の類が悪いんだろう。

>>834
このスレ開いただけでも望みはある！

すごいな。叩きが日常の2chで、ｼﾛｰﾄにここまで優しいのは、久しぶりに見た。

>>838
メモリをイメージする訓練も大切だが、
もっと抽象的に捉える訓練も忘れないで欲しいな。

そうだなー、最近そういうトレーニング怠ってるかも…俺。

>>841
真の文法を書いてる本は稀少なのかね。

>>846
真の文法を書いている本でも、いでおしんくらてっぃくなところは
はしょっているか、読み取れないようにしてるのが多いと思う。
実際、俺なんか、
int typedef integer;
なんて構文が許されるなどとはイソターネットで初めて知った。

なるほど、許されない理由がないから許されるんだな。

もしかして：void main(void)

>>846
真の文法をサポートする本とはLinuxのことである。
Linux以外は紛い物である。

>>833
いや、意味が理解できないなら別にいいんだ。

>>839-841
C/C++ に毒されすぎ (w

文字列と文字の配列が互換の言語はあまり多くないから、
"abcd"[0] を >>834 が奇異に感じるのも無理は無いよ。

[]はmonadの一種でしょ

みなさん、あほな俺に丁寧にありがとう。
さすがに理解できました。

＞多分、そういうコードを今まで見たことが無い、見慣れない、ってだけだろう。
そうですね。はじめてみました。

なんかすっきりしました。
皆さんありがとうございました。

なんかビット演算って難しそうですけど、面白そうですね。
私も、最近処理速度を意識したコードを書く機会があるので
色々参考にします。
（クロックが25KHzなので、処理速度を意識しないといけないんですよ）

ずいぶん遅くない？　8ビット機のときもMHzだったが。。。

ケルビン・ヘルツという単位は寡聞にして知らない。

＞ずいぶん遅くない？
そうなんですよ。1サイクル40usなので、ビット操作（ビットクリアやビットセット）で
7サイクル取られるので、7*40=280us=0.28msもかかるんですよね・・・

えー！　そりゃ遅い。なんだろ。FPGAかなんかか。
最近は組み込みの分野でもJAVAだったりするが、まだまだCの出番はあるってことか。

ボタン電池1個で半年動かすようなものなんじゃね？

>>857
> まだまだCの出番はあるってことか。

て言うか、アセンブラの出番だと思うけど。

Cで書く予定です。アセンブラでは保守のことを考えると難しいので。
如何にCで効率の良いコードを書くか。

クロックを遅くしているのは消費電流の低減のためです。
普段は32MHzで動作しますよ。

>>767-768
ちょっと遅くなったが、求め方が解った。
今回は2^1～2^9だからちょっと変則的なんだが、概念としてはM系列の応用みたい。
なるほどねー。
http://slashdot.jp/~Tellur52/journal/448479

>>861
お前ここに糞スラのURL張るの禁止されていること
しらんのか？

スラッシュドット禁止ってどんだけ情報弱者なんだよ。

え？あっちから拒絶してんの？

あれ？　板ルール？
スマンかった。忘れて。

>>863
あっちも出入りしているけど、そういうことはないと思う。
ここの板ローカルのルールなのかね？
ここも長年見ているが、あまり聞いたことないけど。

>>862はさすがに釣りだろお前ら釣られ杉

ぐぐってもあまりいいページがないんだが、どこかに解説ない？＞M系列

周期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になりますよ、と。ビット溢れによるマスクなども組み合わせているが。

任意の長さのシフトレジスタで適当なタップを選んでフィードバックすれば
最長系列（Ｍ系列）が得られるんだが，
このタップが整数論の方の原始多項式から求められるというのは覚えてる

Cで保守の事を考えずに書いたときに保守しやすいのかといわれればもちろんNOだろ
素人が下手にCで最速コード書くと後で自分で読めないから、最初からアセンブリでやったほうがいいと思う

マクロが使えれば読みやすくなるのも事実だしな
MASMだと、アセンブリの癖にIFだのELSEだの使える。マクロがなければCでプリアセンブラを書けばいいし

安価書き忘れ
>>860

CPU換えたときの心配してるんだったらC

スレタイも読めないバカが多いね。
移植性や保守性を犠牲にしてでも高速化しようってのが趣旨なのに。

書かれてもいない事が見えるバカが居るんだね

【高速化】ビット演算　0x02

やばいですやばいです
ちょっと暴走して勃起が止まりません
リセットできないどうしよう

適切な勃起フラグを提げろ。

トシなのでフラグ立ちません！　どうしよう！

(´･ω･`)知らんがな

＞ 移植性や保守性を犠牲にしてでも

そりゃビット演算すれば多少は移植性が犠牲になるだろうけど、
それだけならぜんぜん問題にはならない。
所詮フラグなんて１本しかないんだからな。
ただまあ、
大きさはいろいろだから互換性がない場合も確かにある。

　＊　 　　　+　　　　巛 ヽ
　　　　　　　　　　　　〒　!　　　+　　　　。　　　　　+　　　　。　　　　　＊　 　　　。
　 　　　　+　　　　。　 | 　|
　　　＊　 　　　+　　 /　/　　　イヤッッホォォォオオォオウ！
　　　　　　 ∧＿∧ /　/
　　　　　　（´∀｀　/　/　+　　　　。　　　　　+　　　　。　　　＊　 　　　。
　　　　　　,-　　　　　ｆ
　　　　　 / ュヘ　　　　| ＊　 　　　+　　　　。　　　　　+　　　。　+
　　　　　〈＿｝ ）　　　|
　　　　　　　 /　　　　! +　　　　。　　　　　+　　　　+　　　　　＊
　　　　　　 ./　　,ヘ　 |　　　　　　このスレッドは８８０を超えました。
　ガタン　||| j　　/　|　 | |||　　　　　　　　次レスも…BITクオリティ！！
――――――――――――　　　　　　 　 http://pc8.2ch.net/tech/


ああ暇だ

ちょっとリンク張らせてクレ。
http://science6.2ch.net/test/read.cgi/math/1209732803/
の427に問題を投稿したんで、暇ならチャレンジしておくれ。

算数得意だけど数学は苦手

http://chessprogramming.wikispaces.com/Bitboards
ここまでくると、なにがなにやら

簡単じゃん

(･∀･) ｶﾞｯｰ

発音できません＞＜

ん？ヌルポはどこ？

>>888
888

又ﾉﾚ木ﾟ

ガッ

力ﾞっ

>>890
その表記、キモすぎるｗ

整数間のキャスト演算について教えてください。
例えば、2の補数で表される4bitの値を8bitに変換する場合、

正の値： 0001 -> 0000 0001 # 最上位bitが0なら上位bitに0000を補う
負の値： 1110 -> 1111 1110 # 最上位bitが1なら上位bitに1111を補う

bit8 = (bit4 & 0x8) ? (bit4 | 0xF0) : bit4;

逆の変換は、

正の値： 0000 0001 -> 0001 # 上位4bitを削除
負の値： 1111 1110 -> 1110 # 上位4bitを削除

bit4 = bit8 & 0xF;

という考え方で合ってます？

合ってる。

どうも

>>894
ARMならプレディケートに展開されるのでそれで十分速いんだが

欲をいえばこっちのほうが命令数とかレジスタ節約できるかもしれないね。
bit8 = bit4 | (bit4 & 0x8) ? 0xF0 : 0;

また、比較命令はall 1 か all 0のビットマスクを生成するタイプのCPUなら、
ビットマスクと0xF0との論理積をとるだけで加算する値を取得できる。


しかし、2項選択は多くのＣＰＵ分岐命令に一般的には遅い。
シフトが遅くないならこっちを試してもいい
bit8 = (signed char)bit4 << 4 >> 4;

現実には多くの32ビットCPUはレジスタサイズ未満のビット演算は遅いのでこっちのほうがいいかも
bit8 = (signed char)(((signed int)bit4 << 28) >> 28);

要はネイティブで算術シフト命令のできる最小単位ならなんでもいい。
同じロジックでbit16でもbit32でも展開できる。

しかし、2項選択は多くのＣＰＵでは分岐命令に展開されるので一般的には遅い。



日本語しゃべれ俺

> bit8 = bit4 | (bit4 & 0x8) ? 0xF0 : 0;

バグってるぞ。

bit8 = bit4 | ((bit4 & 0x8) ? 0xF0 : 0);

これでいいのか？

なるほどsingned型って右シフトで上位ビットを補ってくれるのね。
CPUは普通のPCのIntel x86系です。

x86ならシフト使う方法のほうが有効だろうね（Pentium 4はシフト遅いけど）
bit4 = ecx
bit8 = eax

と仮定して

mov eax, ecx
sal eax, 28
sar eax, 28
and eax, 0xFF

たった4命令で済む。bit4を破壊していいなら3命令。

>>895
ちがうだろ
算術シフトか論理シフトかはコンパイラ依存

100レスくらいで終わってもよさそうなのに実によく伸びるなこのスレ。

まあメジャーなコンパイラならsignedで算術シフトになるけどね。
//でコメントにならないコンパイラ並みには非互換問題あるのかな？

ローテートくらいまではC/C++標準仕様に入れておいて欲しいものだ

分岐は

>>903
> 算術シフトか論理シフトかはコンパイラ依存

負数の右シフトの動作のことを言ってるのか？

>> 2の補数で表される4bitの値を8bitに変換する場合

という条件下なら >>894 の内容に誤りはないと思うが。
そもそも、>>894 のレスにシフトのコードなんてないし。

# レスアンカーが >>897 なら同意するけど、あまり
# 触らない方がいいと思う。

もうこれでええやん
static const signed char table[] = { 0, 1, 2, 3, 4, 5, 6, 7, -8, -7, -6, -5, -4, -3, -2, -1 };

bit8 = table[bit4 & 15];

ダンゴさんの星が落ち着いてきたな

表引きもいいけど、キャッシュ容量とかミスヒットとか気になるし、
算術シフトもちょっと……という場合にはこっちがいいのでは。

bit8 = -(bit4 & 0x8) | bit4

上の動作の流れはこんな感じ。
等幅じゃないと見にくいけど分かってもらえるかな。

src　　　　　temp　　　　dst
????mxyz 00000000 00000000
????mxyz 0000m000 00000000 # temp = src & 0x8
????mxyz 0000m000 mmmmm000 # dst -= temp
????mxyz 0000m000 mmmmmxyz # dst |= src

この程度の小さいテーブルなら表引きは割と効果あるよ。
SSSE3のpshufbやAltiVecのvpermで16並列化もできるし。

>>910
x86で4命令だな。

mov eax, ecx
and eax, 0x08
neg eax
or eax, ecx


ちなみに>>902の方法はこれなら3命令。

mov al, cl
sal al, 4
sar, al 4

ただ、とてつもなくパーシャルレジスタストールの臭いがするぜ

Cで上手いことローテート命令に割り当てられるような書き方って何かある？
今は、8ビットローテートの場合は

(val << num) | (val >> (8-num) )

って書いてるけど、アセンブラ見てもまんまシフトとORで作られるんだよな
最後の手段でインラインアセンブラ使ってるけど、誰かＣでいい書き方知ってたら教えてくれ

そもそもローテート演算子がないからローテートを出力するコンパイラがないんじゃ

gccなら
unsigned foo(unsigned x, int n) {
return (x << n) | (x >> (32 - n));
}
で↓になったよ
_foo:
movl 4(%esp), %eax
movl 8(%esp), %ecx
roll %cl, %eax
ret
8ビットは無理だた

ダンゴさんならローテートの速度について一言ありそうだな

あぁ、コンパイラのオプション弄ったらちゃんとローテートになったわ
ちなみにCPUはARM、コンパイラはARM製のコンパイラです
速度に関しては何ビットローテートしても1クロックで済む、RISC万歳

>>914
インラインアセンブラで書いたものを、インライン展開できるようにしておくのはダメなの？
インラインの関数呼び出しでは不満？
演算子でやりたいなら、演算子をインライン展開できるように定義すればいいだけだと思うが。

>><とか <<>とかみたいな演算子を逆輸入してくれれば良いんだがねぇ

無理に演算子にしなくても、
コンパイラが認識する組込関数にすれば十分だよ。

このほうがローテートっぽい
@>
<@

>reg>
<reg<

㊨
㊧

_lrotr
_lrotl

|>
<|

>>925
指輪物語?
>>926
シュレディンガー音頭?

記号の演算子じゃなくて普通に単語使えばいいのに

ばかでしょ

指輪物語はlotrだなｗ

>>929
tlotr

公式はLOTR

なんで指輪物語スレになってんの・・・

>>931
tlotr

ググれば一目瞭然。

The Lord of the Rings だし。

Lordsな。両方複数系。

http://www.lordoftherings.net/
つまり、オフィシャルサイトは間違っていると。

>>935
Lordが正しい。
>>936
「the」がないのは、ドメイン取得の問題じゃないかな。

何時の間にか指輪スレ化している流れを豚切。

man gawk を見ると
lshift, rshift って内部関数が実装されているんだな。

>>925もVC++独自のローテート関数なわけだが。
指輪とはあんまり関係ない。

指輪物語とまで云うならthe fellowship of the ringだろ

lotrをロートルと呼ぼうのスレはここですか？

>>940それ第１章の副題

>>941
何…だと……？

>>933
lotr の検索結果 約 9,330,000 件中 1 - 10 件目 (0.15 秒)
tlotr の検索結果 約 69,400 件中 1 - 10 件目 (0.17 秒)

一体何が一目瞭然なんだか。

>>937
> 「the」がないのは、ドメイン取得の問題じゃないかな。

レスするなら、URL だけじゃなくてちゃんとページ見ろよ。

省略形で定冠詞を省略するのはごく普通。
２個あるうちの片っぽだけというのはちょっと違和感あるけど。

流れぶったぎって次スレ案

【指輪】ビット演算　0x03【物語】

いや、つまんないから

つーかもうスレ自体不要

>>944
これはコラだね、俺は騙されんよ。

>>947
>>945

>>948
>947

>>944-950
>>9

>>943
それは省略形であって正式ではない。
テレビジョンよりテレビの方がヒットするのは当たり前だろ。アホか。

0を移動していくシフト演算っていい方法ある？

111111011
↓
111110111
↓
111101111
↓
111011111

こう言う感じで

a << 1
a | 1

>>953
速レスサントス

逆に考えるんだ
1のほうを立てて

00000100
↓
00001000
↓
00010000
↓
00100000

参照するときに反転すればいいと考えるんだ

ttp://www.amazon.co.jp/gp/product/images/0618002251/

>>951
> それは省略形であって正式ではない。

一体何を言ってるんだ？

> テレビジョンよりテレビの方がヒットするのは当たり前だろ。アホか。

アホはお前だよ、単語の区切ぐらい見てるだろ。

yaho の検索結果 約 2,580,000 件中 1 - 10 件目 (0.06 秒)
yahoo の検索結果 約 2,330,000,000 件中 1 - 10 件目 (0.08 秒)

そもそも、どうやって「ググれば一目瞭然」なのか >>933 に聞けよ、クズ。

マジで>>944か>>946でいいような気がしてきた
もうどうでもいいよ

それ省略になってないし

>一体何を言ってるんだ？
あの文章に対してこんな事言ってるようじゃ
やはり>>957が真のアホと言わざるを得ない

何？悔しかったの？ｗ

　　_..,,.,,.
　 「r',.　、
　d　´c`/　ちくしょう・・・
　 i　' ∋

ぉち 彡　,.-,ﾆユ、
ぉ く .三　 { ,.= r、
｜し 三 (6' r',ニ7
｜ょ 三.　| !| {　{
｜お 三. |　ﾐ‐ニ)
! ! ぉ ミ　!　　　{

>>960
>> テレビジョンよりテレビの方がヒットするのは当たり前だろ。アホか。

いや～、賢いねぇ。(w

よく>>751-752の課題を見ると、aが整数だとはどこにも書いてなかったな。
だから、>>763の方法で計算できるのは、aに近い整数値でしかない。
それに、渡さされる2^aの値が整数かどうかも記載されていないな。

ビット演算だから常に整数という誤認があったかもしれん。
まあ、小数点以下の計算も整数演算の延長でしかないから問題ないけど。

32bit整数でビットが立ってる最上位のビット以下を全部立たせる処理で
int fill(int n){
　　n |= n>>1;
　　n |= n>>2;
　　n |= n>>4;
　　n |= n>>8
　　n |= n>>16;
　　return n;
}
てのを作ってみたんだが、まだ速くできるかな？てか、この処理に名前ってある？

>>965
アセンブラ使っていいなら２命令で終わり。

それ無しでｗ

gccの拡張使っていいなら
int fill(int n) {
return n ? (~0u >> __builtin_clz(n)) : 0;
}

>>968　それって結局どんなコードになってるんですか？

bsr

n|n-1で行けない？
n=0の時上手くいかないだろうけど。

それでうまくいくのnが２のべき乗のときだけじゃない？

4(or8)毎に処理するとか？

bsrってaddとかと同じレベルの命令？その命令って最近のCPUにはどれでも入ってるって言うのかい？