というわけでnextCombination()を組んでみました。
bsf( b + 1 ) = 32 - cntlzw( b )を使ってます。
結果は
C verion(割り算あり)
PIII 40clk
PPC 31clk
C version(割り算回避)
PIII 29clk
PPC 26clk
asm
PIII 13clk
PPC 21.5clk

なお、PPCは初めてのプログラミングなのでご了承。
ついでにclockも正確なのかはわかりません(^^;
で、感想ですが、PPCってめっちゃ組みやすい。
OSがあれなのがちょっとあれですが(^^;

>もう解けたので
>いいです。
あいかわらず台詞回しやな(^^;

>実行させたりするの無しね。
しばらく考えたけど分からなかったので実行してしまいました。
%2551443があるので○に関係あるものかなと想像していたのですが
結果を見てもすぐには意味がわかりませんでした。
ソースを見直してようやく納得。いや驚きました。
#ソースだけで分かる方ってどのぐらいいらっしゃるのかな。

でもこれ、2/22あたりに実行していたら正常動作してないのかな
としか思えないでしょうね。

いいです。

東大のときの後輩がIOCCC(http://www.ioccc.org/)で入賞した。
こんなプログラム

#include <stdio.h>
#include <math.h>
double l;main(_,o,O){return putchar((_--+22&&_+44&&main(_,-43,_),_&&o)?(main(-43
,++o,O), ((l=(o+21)/sqrt(3-O*22-O*O),l*l<4&&(fabs(((time(0)-607728)%2551443)/405
859.-4.7+acos(l/2))<1.57))[" #"])):10);}

実行させたりするの無しね。俺まだ解いてないから、分っても
答をこの掲示板で発表するのも無しね。

一般には bsf と cntlzw の結果には法則性がないので、
cntlzw をフルに使うには逆向きしかないですね。
ただ、引き算の換わりにExORを使うことになるので、み、の
気に入る"分りにくさ"がなくなると思うよ。

> >オンラインで命令一覧表とかリファレンスとかないでしょうか？
> http://www.intel.co.jp/jp/developer/design/pentiumIII/manuals/index.htm
> AMDが日本語のを出してるのは見たことないです。あるのかなあ。

ありがとうございます_(__)_
IAって何の略だろうとか思ってましたが、IntelArchitecture
の略なんですね(^^;
＃んなもん略すなよな＞IntelHomepage

Enhanced3DNowとかも気になりますよね(^^
アセンブラは一度やったら止められませんね。

タイトルの意味を理解するのに時間がかかった(^^;
そういや、そうですね。
一般には言えないけど今の場合は成り立つのか。
逆向きの方は...これからゆっくり考えます。

uint32 const msb = 1 << 31;
unit32 const msb2 = 3 << 30;

....

if( a & msb ) {
　/* あとで考えよう */
} else {
　a ^= msb2 >> cntlzw( a ) - 1;
}

というのでは？( - は >> より優先されることに注意 )
# 全角スペースでインデントしてみました。

bsf( b + 1 ) は 32 - cntlzw( b ) に等しい、というのでは
どうでしょう？

私も最初は剣聖炎羅さんみたいなコード書いて何とか
ならないかともがいてました(^^)
このコードも確か他の方に教えて貰ったはずです。
同じ命令数なのにさ〜さんのと微妙に違うのが面白いですね。

>CFって桁あふれがあった場合に1になるんでしょうか？
Carry Flagですから当然そうなります。

>オンラインで命令一覧表とかリファレンスとかないでしょうか？
http://www.intel.co.jp/jp/developer/design/pentiumIII/manuals/index.htm
AMDが日本語のを出してるのは見たことないです。あるのかなあ。

> 後半部分です。
> 　add ebx, 0xFFFFFF00
> 　sbb edi, edi
> 　or ebx, edi
> 　and ebx, 0x000000FF
> でどうでしょうか。
　うわー、orなんて考えもしなかったです。
　マスクっつったらandだろー。って思考回路でした(^^;

　CFって桁あふれがあった場合に1になるんでしょうか？

> sub ebx, X
> sbb edi, edi ;edi=(ebx-X>=0)?0:-1
> and ebx, edi ;ebx=(ebx-X>=0)?0:ebx-X
> add ebx, X
なんて綺麗な(^^　やはり私はまだまだ未熟です。

> subのCF変化を見逃したのが少し甘かったですね(^^;
subでも変化するんですね（当たり前か(^^;）
VC++のレジスタ表示ってCFの表示がないんですよね。
ところで、オンラインで命令一覧表とかリファレンスとか
ないでしょうか？
＃有力なところで、Intelから(^^;

このあたりのネタは以前話題になったのですが、
忘れてしまいました(^^;
一覧表を作っておかないと駄目ですね。

>もうちょっといい方法があるような気がしてなりません(^^;
X以上のクリッピングはこんな風だったかな。
sub ebx, X
sbb edi, edi ;edi=(ebx-X>=0)?0:-1
and ebx, edi ;ebx=(ebx-X>=0)?0:ebx-X
add ebx, X

subのCF変化を見逃したのが少し甘かったですね(^^;

ちわ、マスクマニアのさ〜です(^^;

後半部分です。
　add ebx, 0xFFFFFF00
　sbb edi, edi
　or ebx, edi
　and ebx, 0x000000FF
でどうでしょうか。

こんにちは、剣聖炎羅です。
レジスタ３つで無理矢理クリッピングしてみたんですけど
いかがでしょう…(^^;
ebx = 元値です。
//Green成分のクリッピング
cmp ebx, (1<<31)//CF = ( ebx >= 0 ) ? 1 : 0;
sbb edi, edi //edi = ( ebx >= 0 ) ? -1 : 0;
and ebx, edi //ebxの0以下をクリッピング
xor edi, edi
sub ebx, 255
cmp ebx, (1<<31)//CF = ( ebx-255 >= 0 ) ? 1 : 0;
adc edi, -1 //edi = ( ebx-255 >= 0 ) ? 0 : -1;
and ebx, edi
add ebx, 255 //ebxの255以上をクリッピング

もうちょっといい方法があるような気がしてなりません(^^;

parmitationじゃなくてpermutationですね。
更にそもそもcombinationの間違いでした(^^;
それからtabとかspaceってどうすれば入力できるのかな。
読みにくくて仕方ないです。

かなり昔に一風変わった組み合わせのプログラムを作ってましたよね。>dsk

それはこんなものです。
ぱっと見て何をやってるのか分からないところが気に入ってるのですが(^^;
割り算が入ってるのがちょっと悔しかったのです。

(c&-c)/(b+1)は本当は単なるシフトなので
a = c&-c;
while(b){a >>= 1; b >>=1;}
return c - a;
で実現できるけど、あんまりかっこよくない。

ただx86にはbsfという0bitから探して初めて1がたったビットの位置を返す命令があるので
それを割とスマートには書けます。
bsf ecx,"b+1"
shr "a",cl ;"a"を右にshift

ところで、昨日PowerPCのマニュアルをぽけっと眺めてるとなんとcntlzw なる命令を発見。
「RISCチップの癖に???」と驚いたのですが残念ながら最上位bitから探索する(bsfと向きが逆)ためそのままでは使えません。
# `0'なら32, '1'なら31, '5'なら29が返ります。

;さて、この命令を前提としたコードってかけますかね。
#滅茶苦茶強引なネタ振りだなあ(^^;

typedef unsigned long uint32;
uint32 nextParmitation(uint32 a){
uint32 b,c;
if(a & 1){
b = a ^ (a+1);
c = a - b/2;
return c - (c & -c) / (b+1);
}else{
return a - (a & -a) / 2;
}
}

void printB(uint32 a){
int i;
for(i=0;i<32;i++){
printf("%d",1 & (a>>(31-i) ) );
if((i+1)%4==0)printf(" ");
}
printf("\n");
}

int main(void){
uint32 i,n,k;
n = 6;
k = 2;
/* 11...100....00
* <- k個->
* <--- n個 ---->
*/
i=((1<<(n-k))-1)<<k;
while(i){
printB(i);
i=nextParmitation(i);
}
return 0;
}

>そしてまた　それを再生するプレーヤーがまちまち。
>おまけにパソコンでしか再生できない。
WinAmpとプラグインで大抵の形式には対応できると思います。
普通のCDプレーヤで再生するにはwav形式にしないといけないですが、
それはWinAmpの出力設定をwav形式にすればよいです。
詳しい方法については"WinAmp"や"wav出力"などのキーワードで
検索すれば沢山解説pageが見つかりますからそれを参考にしてください。

初めまして・・・・
今年は音楽に挑戦しようと思ってる40過ぎのおじさんです。

実は　子供にせがまれてネットから好きな曲をダウンロードして
CDに書き込み、机上のCDプレーヤーで聞けるようにしたいのです。

今年になってからはや一ヶ月が過ぎましたが、まだ手探り状態です。

まず、認識不足だったのが音楽ファイルの種類の多さ。いろんな拡張子があって驚いています。。
そしてまた　それを再生するプレーヤーがまちまち。おまけにパソコンでしか再生できない。（勘違いしてますか？）

それを変換してCDに焼かないと机上のCDプレーヤーでは再生できないのですよね？変換もどのファイル形式に変換したらいいのかわからず、もう投げ出したくなりました。

しかし！

常日頃子供に相手して貰う事もない私にとって　この事は株を上げる唯一の手段！なんとかしたいのです。お金が掛からず（極力です。多少は致し方ないと思っています）私の思う事ができるのでしょうか？
それすら不安になってきました。

それから最近の若い娘の好みの曲というのは　一体どこに行ったらダウンロードできるのですか？もうあっちこっちネットサーフィンしました皆目見当がつかず　お手上げ状態です。新しい曲などは著作権の問題もありますからCDを買うのと同じくらいお金は掛かるだろうと承知してますが。

なんとか　お助けくださいませんか？？

追記しておきますが　私のパソコンは　ソーテックの260RWです。
書き込みソフトは「 Adaptec Easy CD Creator 4.02 Standard 」です。
CDからCDへのコピーはしたことがあります。

宜しくご教授ください。

ご無沙汰してます、剣聖炎羅です。
なにやら汎用的なお話が。
こういうのってすごく勉強になります。

アホな投稿ですみません(^^;;;

めっちゃ恥ずかしい(^^;
思いっきり勘違いしてました。

単にtopとbottomの場所を覚えておけばいいんですよね。
さ〜さん
>よって、テーブルサイズは
>(MAXN+1) * MAXN - (MAXN-1)
>となるかと思います。
そうですね。整理してMAXN^2 + 1

dskさん
>音声再生のルーチンを解析しているときに(私が見たのは
>MacOSのAPIの中身)この実装を見つけました。

自分でも音声再生+生成時に実装してました。
なんで複雑に考えちゃったんだろう...

↓は全然普通の実装じゃないみたいですね。
やっぱり普通はlistのようです。ここの話題の、サイズ制限の
あるキューは、通常の用途には向かないようです。

一つ大きな配列にすることにより、queueが空の状態と、満杯の
状態を区別することが出来るということです。即ち、
qTop == qBot
が空の状態、
qincrement[qTop] == qBot
が満杯の状態、となります。この実装で、状態遷移をすべて持つ
よりもメモリも速度も効率良いと思いますが......

音声再生のルーチンを解析しているときに(私が見たのはMacOSの
APIの中身)この実装を見つけました。qincrement[]は使っていな
かったことと、qsizeの値にかかわらず、配列の大きさが128(
したがってqsize <= 127)であったことをのぞけば同じです。

# qsize + 1 が 2のべき乗ならqincrementを使わないほうが速い
# ですね。

コンストラクタの qdata( qsize ), qincrement( qsize )は、
それぞれ、qdata( qsize + 1 ), qincrement( qsize + 1 )に
訂正して下さい。

C++で、stlのstd::vector<>クラスを使った実装は、次のような
感じになります。C++な人はこっちのほうが分りやすいかも。

#include <vector>
using namespace std;

template<class T>
class Queue {
public:
Queue( int qsize ) : qTop( 0 ), qBot( 0 ), qdata( qsize ),
qincrement( qsize ) {
for( int i = 0; i <= qsize; ++i ) qincrement[i] = (i + 1)%(qsize + 1);
}
void enq_nocheck( T const& d ) {
qdata[qTop] = d;
qTop = qincrement[qTop];
}
bool enq( T const& d ) {
if( qincrement[qTop] == qBot ) return false;
enq_nocheck( d );
return true;
}
void deq_nocheck( T& d ) {
d = qdata[qBot];
qBot = qincrement[qBot];
}
void deq( T& d ) {
if( qTop == qBot ) return false;
deq_nocheck( d );
return true;
}

protected:
vector<T> qdata;
vector<int> qincrement;
int qTop, qBot;
};

queueの普通の実装は、ひとつ大きいサイズの配列を用います。
queueのサイズを qsize queueのデータを datatype とすると、
次のようになります。C++は我慢してCで書いてみます。

int const qsize = 100;
typedef struct { ..... } datatype;
datatype qdata[qsize + 1];
int qincrement[qsize + 1], qTop, qBot;

int const True = 1;
int const False = 0;

#define enq_nocheck( d ) do {\
qdata[qTop] = d;\
qTop = qincrement[qTop];\
} while( False )

#define deq_nocheck( d ) do {\
d = qdata[qBot];\
qBot = qincrement[qBot];\
} while( False )

void init() {
int i;
qTop = qBot = 0;
for( i = 0; i <= qsize; ++i ) qincrement[i] = (i + 1)%(qsize + 1);
}

int enq( datatype const* d ) {
if( qincrement[qTop] == qBot ) return False;
enq_nocheck( *d );
return True;
}

int deq( datatype* d ) {
if( qTop == qBot ) return False;
deq_nocheck( *d );
return True;
}

こんちわ。

予稿の現実逃避のプレゼンの現実逃避に。(笑)

この場合のテーブルサイズの求め方は既知なのでしょうか。
とりあえず、僕は知らないのでちょっと考えてみました。

pushのターゲット数：MAXN+1 {-1 < n < MAXN }
pop のターゲット数：MAXN+1 {-1 < n < MAXN }
ただし、push==popはないので、単純計算すると
(MAXN+1) * MAXN
になります。

が、しかし・・・
queの中身が空の状態になった場合にはpushのターゲット
位置に関わらずstat=0にすることができます。
この場合が何通りあるかと考えてみると、
push:0〜(MAXN-1)
pop :-1
の場合が該当するため、
MAXN通りの状態は1通りにまとめることができることになります。
よって、テーブルサイズは
(MAXN+1) * MAXN - (MAXN-1)
となるかと思います。
というのはMAXN=2のときのテーブルサイズ5になるように
考えました(弱っ

どんなもんでしょうか。

#5日東京方面に行ってました。dskんちにもよりたかったけど疲れてたので断念。

さて普通はlist構造を使って実現するのだけど、queが溜まる最大数(=MAXN)が予め分かっている場合はテーブル引きで実現できますよね。
例えばMAXN=2の時はqueBuffer[2]を用意して
状態遷移を表す
static struct{
int push, pop;/* ターゲットqueBuffer */
int up;/* up後のqueTbl */
int down;/* down後のqueTbl */
} queTbl[5] = {
{ 0, -1, 1,-1},
{ 1, 0, 2, 0},
{-1, 0,-1, 3},
{ 0, 1, 4, 0},
{-1, 1,-1, 1},
};/* -1はありえない遷移状態 */
と現在のequTblを指す stat(初期値0) を使って
pushは
idx=queTbl[stat].push;
queBuf[idx]=pushすべきデータ
stat = queTbl[stat].up;/* 状態更新 */

popは
idx=queTbl[stat].pop;
popされたデータ=queBuf[idx];
stat = queTbl[stat].down; /* 状態更新 */
ただこの方法だとMAXN=8のときを実現したい場合はqueTblのサイズが莫大になるので非現実的。
テーブル引きを複数回に分けてサイズを小さく出来ますかね。
真剣に考えたこと無いので簡単なのかどうか分からないのですが。
後このテーブルを自動生成するアルゴリズムも欲しいな。
誰かヘルプ(^^;

回答ありがとうございます。質問者ぺぺです。
ちなみにL1と書くつもりがL!となってて私もびっくりです。

> > Ｌ１とレジスタの間ってそもそも「バス」なんて構造になってる
> > のでしょうか？
>
> 　レジスタに書きこめるのはLoad Unitの他に実行Unit系もあるので、
> レジスタへの入力線は共有されてるだろうと「勝手に」思いこんで、
> バスと言う言葉を使いました。
> 　Load Unitから実行Unitを通じないとレジスタに書き込めない構造で、
> 実行Unitが1つしかないと共有しないのでポートになるような気もしますが。
> （古典的なRISCはこんな感じだったかな…）
>
えーと、そもそもバス構造になってるというのが間違いということでしょうか。長船さんのレスにあるロウとカラムって言うのがメモリセルアレイでいうところのロウとカラムを指すならロードストアユニットがセレクタのようなものでそこから先はそれぞれのレジスタにつながってる
ということですか。ロウが指定されるとロウにつながるデータがすべてセレクタに出力されるみたいにロードストアユニットに出力されると。

うーむ どうもキャッシュというとひとつの記憶ユニットという感じがあったのでL1キャッシュの出口は共通のバスみたいなものだと思ってました。

> > Pentuim以降、Ｌ１データキャッシュにあるデータは１クロックで
> > レジスタにロードされるわけですが、それをどんな手段で行うか
> > は設計思想の問題なので、プロセッサの設計者でないと判りませ
> > んね。
>
> 　やっぱり、そうですよね。
> 　ユーザの立場では必要のないレベルの情報なんで公開して
> くれそうもないですしね。

でもやっぱり詳しいことはプロセッサの設計者に聞くしかないということですね。でもそれって誰に聞けばいいんでしょう？まーたしかにユーザレベルでは必要のない話ではあるのですけど。もしかしたらメモリにデータを書くまでに無駄なところがあるのかと思いまして。

どうも本当に回答ありがとうございました。

俺たちの代で、京大情報工の実習から、KEACの実装が最後になった
んだよね。KEACとは8bitのCPUで最低実装すべき命令セットだけが
与えられた仕様で、後は設計から実際に作るまでをグループで
やらされた。あの実習は目茶苦茶辛かったけど(しかも同時にRIMS
に入る為の試験勉強もしていた俺は今思えば無謀だったかも)役に
立つものであったと思うよ。

> Ｌ１とレジスタの間ってそもそも「バス」なんて構造になってる
> のでしょうか？

　レジスタに書きこめるのはLoad Unitの他に実行Unit系もあるので、
レジスタへの入力線は共有されてるだろうと「勝手に」思いこんで、
バスと言う言葉を使いました。
　Load Unitから実行Unitを通じないとレジスタに書き込めない構造で、
実行Unitが1つしかないと共有しないのでポートになるような気もしますが。
（古典的なRISCはこんな感じだったかな…）

> Pentuim以降、Ｌ１データキャッシュにあるデータは１クロックで
> レジスタにロードされるわけですが、それをどんな手段で行うか
> は設計思想の問題なので、プロセッサの設計者でないと判りませ
> んね。

　やっぱり、そうですよね。
　ユーザの立場では必要のないレベルの情報なんで公開して
くれそうもないですしね。

長船です。

Ｌ１とレジスタの間ってそもそも「バス」なんて構造になってる
のでしょうか？
Pentuim以降、Ｌ１データキャッシュにあるデータは１クロックで
レジスタにロードされるわけですが、それをどんな手段で行うか
は設計思想の問題なので、プロセッサの設計者でないと判りませ
んね。

個人的な推測では４ウェイセットのキャッシュの場合、１ロウが
４カラム(64ビット幅)で構成されているので、256ビット幅の
カラム線がロードストアユニットまで伸びていて、そこでどの
レジスタのどこにカラム線を繋ぐかのセレクションが行われている
のではないかと思います。

どうもお久しぶりです。
こう言う話は私は分かりません(^^;
#ならコメントするなって

>レジスタと他を結ぶバスですが、レジスタ幅よりバス幅の方が
>広くても使い道がないのでしょう。
>ですから、レジスタ幅以下の幅のバスだと思います。

P5の頃メモリ転送にFPUを使えば速くなるという話がありましたが
486では逆に(かなり)遅くなってました。
doubleを16bit4回で送ってたのかもしれませんね。
#↑まったくとんちんかんな事言ってるのかも。信用しないでね。

PS.
最近妙に忙しいです。
今週末は少し時間が取れる筈なのでまた
せこい最適化のネタを考えたいものです。

　どなたか詳しい方がお答えになるかと期待していたのですが…。
　とりあえず、私は「レジスタってFFでできてるかどうか」さえ知らないレベルなんで全面的に信用しないように…。

　L1キャッシュ（レジスタを相手にするからデータキャッシュでしょうね）とレジスタは直接は結ばれていません。
　結ばれ方には大まかに分けると２パターンあるようで
1.[L1 Data Cache]-[Load/Store Unit]-[Execute Unit]-[Register]
2.[L1 Data Cache]-[Load/Store Unit]-[Register]
といった感じです。
　[Load/Store Unit]は兼用の場合と[Load Unit]と[Store Unit]にわかれている場合があります。
　1.のパターンがP5系/6x86系/WinChip系/K7系で、2.のパターンがP6系/K5系/K6系/NB系です。
　x86互換以外のアーキテクチャには詳しくないのですが、大体この2パターンにはまっていたと思います。

　レジスタと他を結ぶバスですが、レジスタ幅よりバス幅の方が広くても使い道がないのでしょう。
　ですから、レジスタ幅以下の幅のバスだと思います。
　ただし、そのバスが複数ある可能性は大いにあります。
　ちなみにレジスタ幅よりバス幅が小さい場合は複数回の転送でアクセスを実現します。

　以上のような感じだと思います。
　まだ、判らないことがございましたら書きこんでみてくださいませ。
　今度こそ識者の方のご回答があるに違いありませんから…と責任逃れ（笑）
　また、それは間違っているというご指摘もよろしくお願いします＞識者の方々

どうもはじめまして。ちょっとお聞きしたいことがあるのですがなにぶん初心者なのでそのあたりはご配慮ください。
じつはここの過去Log300台のべっちさんと似たような疑問を持っているのですがCPUのレジスタにつながるバス幅ってアクセス単位の違い（charとかint）によって有効に利用されていないのでしょうか？
というのはおそらくメモリからL2キャッシュとL2からL1キャッシュ間はブロック転送により３２byte転送されるからバス幅をフルに活用できていると思うのですがL1からレジスタまでがどうなっているのかよく分かりません。
やっぱりバス？が64ビットあってもchar型のデータを転送するとと1バイト分しか駆動しないのですか？そもそもレジスタとL1キャッシュ間のバス幅ってどれくらいなんでしょうか。

どうも本当はINTELのデータシートを見れば分かる話なのでしょうがあんまり英語が得意じゃないので、もし知っていらっしゃったらでいいのでご教授お願いします。

バグフィックスのつもりがバグフィックスになってなかっただけ、
のことでしょう。MSだし。

そういや以前Win2kのコンソールでargvの解釈が変というのが
ありましたが、こないだservice pack1を当てたので直った
のか試してみました。("t t.exe"は引数を表示するプログラム)

以前は動いて(変な値を出していた)
>..\tmp\"t t.exe" 1 "2 3" "4 5 6"
が
Unmached quote
というエラーになったので「お!直ったのか」と思ったのもつかの間
>".."\tmp\"t t" 1 "2 3" "4 5 6"
では
0:`D:\TMP\TTB434~1.EXE' (<="t t.exe"のshort file name)
1:`\tmp\t t'
2:`1'
3:`2 3'
4:`4 5 6'
と(前回と挙動が違うながらも)変。(笑)

しかし
>"t t" 1 23"4 5" "6 7 8"9
だと
0:`D:\TMP\TTB434~1.EXE'
1:`1'
2:`234 5'
3:`6 7 89'
となって引数にある"の処理は正常に行われているのがなんとも。

service pack2が出たら、また仕様が変わってるんだろうな...

最近はTCPの基本的なプログラムの勉強してます。
ネットワークは結構楽しいですな。

まだまだ忙しくなるであることよ。