とある課題解決に協力していただけませんか？

[newgate]

自分は今、とある数NAに対してある状態遷移行列を表示するプログラムに取り組んでいます。
現状のソースコードは以下です。

コード:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define NA 4          /* NA=3,11禁止 */

int main(void)
{
    int NB = NA - 1;     /* NB = 2 */
    int an = pow(2,NB);  /* an = 4 */
    int NC = an / 2;     /* NC = 2 */
    int a[an][an];
    int l,k,m;
    for(l=0;l<an;l++)  for(k=0;k<an;k++)  a[l][k]=0;

    k = 0;
    for(l=0;l<NC;l++){
        a[l][k]=1;
        a[l][k+1]=1;
        k=k+2;
    }
    k = 0;
    for(l=NC;l<an;l++){
        a[l][k]=1;
        a[l][k+1]=1;
        k=k+2;
    }

    printf("a[%d][%d]={",an,an);
    for(l=0;l<an;l++){
        printf("{");
        for(k=0;k<an;k++){
            printf("%d",a[l][k]);
            if(k!=an-1){
                printf(",");
            }else{
                printf("}");
                if(l!=an-1) printf(",");
            }
        }
        if(l!=an-1) printf("\n         ");
    }
    printf("};\n");
}

実行結果は以下のとおりです。

コード:

a[8][8]={{1,1,0,0,0,0,0,0},
         {0,0,1,1,0,0,0,0},
         {0,0,0,0,1,1,0,0},
         {0,0,0,0,0,0,1,1},
         {1,1,0,0,0,0,0,0},
         {0,0,1,1,0,0,0,0},
         {0,0,0,0,1,1,0,0},
         {0,0,0,0,0,0,1,1}};

ここから、二進数表記にした場合に「11」を含む状態からの遷移や、「11」を含む状態への遷移を除外したいのですがどうすればいいのでしょうか？
この場合は、「011」「110」「111」が該当する状態なので、「011」→「3」、「110」→「6」、「111」→「7」から、上記から除外するのはa[1][3],a[3][6],a[3][7],a[5][3],a[6][4],a[6][5],a[7][6],a[7][7]となり下記のようにしたいということです。

コード:

int a[8][8]={{0,1,0,0,0,0,0,0}, 
             {0,0,1,0,0,0,0,0},  
             {0,0,0,0,1,1,0,0}, 
             {0,0,0,0,0,0,0,0}, 
             {1,1,0,0,0,0,0,0},  
             {0,0,1,0,0,0,0,0},  
             {0,0,0,0,0,0,0,0}, 
             {0,0,0,0,0,0,0,0}}; 

どうすればいいでしょうか。

[beatle]

上記から除外するのはa[1][3],a[3][6],a[3][7],a[5][3],a[6][4],a[6][5],a[7][6],a[7][7]

とありますが、a[0][0]が除外される理由を教えて下さい。

[newgate]

すいません、こちらのミスですね。

コード:

a[8][8]={{1,1,0,0,0,0,0,0}, 
             {0,0,1,0,0,0,0,0},  
             {0,0,0,0,1,1,0,0}, 
             {0,0,0,0,0,0,0,0}, 
             {1,1,0,0,0,0,0,0},  
             {0,0,1,0,0,0,0,0},  
             {0,0,0,0,0,0,0,0}, 
             {0,0,0,0,0,0,0,0}};

が正しいはずです。

[beatle]

まず、あるint型の変数に入っている数値が、11の連続を含むかどうかを判定する関数を作ってみましょう。
xをint型の変数とし、そのiビット目が1かどうかを判定するには

コード:

if ((x >> i) & 1 != 0) { /* iビット目は1 */ }

となります。

[newgate]

その場合、変数xは変化してしまっているということでしょうか？

[non]

状態遷移行列ってのは知りませんが、要するに

コード:

for(i=0;i<an;i++)
	for(j=0;j<an;j++)
		if(iが11を含むか または　jが11を含むか)
			a[i][j]=0;

こうしたいって、ことなのでしょうか？
で、beatleさんが関数を作ってみようって提案しているのは、
プログラムの「iが11を含むか」って関数
その一歩として、指定ビットが1か調べる関数ってことでしょう。
だから、xはiが渡された仮引数になる。

[beatle]

nonさんの仰る通り、僕が提案したのは「引数に渡された整数の2進数表現の中に、11が含まれていたら真を返す関数」です。
その関数のプロトタイプは次のようになるでしょう。

コード:

int Contains11(int x);

引数x : 2進数表現をしたときに11が含まれるか調べたい整数値
戻り値 : 11が含まれるなら非0、含まれないなら0

この関数は次のように使います。

コード:

for(i=0;i<an;i++)
    for(j=0;j<an;j++)
        if(Contains11(i) || Contains11(j)) /* iが11を含むか または　jが11を含むか */
            a[i][j]=0;

「その場合、変数xは変化してしまっているということでしょうか？」という質問が何を意味しているのか、よく分かりませんでしたが、以上の回答で答えられていますでしょうか。まだ疑問なことがありましたら、もっと分かりやすく質問していただければと思います。

[たかぎ]

nonさんの仰る通り、僕が提案したのは「引数に渡された整数の2進数表現の中に、11が含まれていたら真を返す関数」です。
その関数のプロトタイプは次のようになるでしょう。

コード:

int Contains11(int x);

引数x : 2進数表現をしたときに11が含まれるか調べたい整数値
戻り値 : 11が含まれるなら非0、含まれないなら0

これって意外に実装するのは難しいですよね。

コード:

int Contains11(int x)
{
     unsigned int y = *(unsigned int*)&x;

     for (int i = 0; 2u << i; i++)
          if (((y >> i) & 3u) == 3u)    // 0b11 == 3
               return 1;
     return 0;
}

特定の処理系に特化させるなら、もう少し簡単になるかもしれません。

[たかぎ]

よく考えたら負値は考慮する必要がないので、汎用的なものにするのでなければそう難しくありませんね。

[non]

たかぎさん。こうした方が良い理由ってなんですか？

コード:

     unsigned int y = *(unsigned int*)&x;

これでは拙い場合って？

コード:

     unsigned int y = (unsigned int)x;

教えてください。

[たかぎ]

たかぎさん。こうした方が良い理由ってなんですか？

コード:

     unsigned int y = *(unsigned int*)&x;

処理系不明ですので、負値の内部表現がわからないからです。

[non]

処理系不明ですので、負値の内部表現がわからないからです。

負数のためというのは、前の投稿でもわかりましたが、なぜ、この表現でクリアできるのかというのが
よくわからないのです。

例えば負数が8ビットで表される場合、
10進5は
00000101
-5は
２の補数なら
11111011
１の補数なら
11111010
最上位ビットが１のとき負数なら
10000101
他に処理系によって違う内部表現があるのかは知りませんが、
これらを　単純にunsigned int　にキャストした場合と、変数の型を変えてから代入する場合とでは
どう変わるのでしょうか

[たかぎ]

処理系不明ですので、負値の内部表現がわからないからです。

負数のためというのは、前の投稿でもわかりましたが、なぜ、この表現でクリアできるのかというのが
よくわからないのです。

例えば負数が8ビットで表される場合、
10進5は
00000101
-5は
２の補数なら
11111011
１の補数なら
11111010
最上位ビットが１のとき負数なら
10000101
他に処理系によって違う内部表現があるのかは知りませんが、
これらを　単純にunsigned int　にキャストした場合と、変数の型を変えてから代入する場合とでは
どう変わるのでしょうか

符号付き整数→符号無し整数型に変換する場合、元の値が表現できなければ、結果の型の最大値+1を法とする剰余になります。
つまり、元の符号付き整数型の負値の内部表現がどうであるかに関わらず、必ず2の補数になってしまいます。
これを回避するには、今回のようにポインタを介して型を再解釈させるか、共用体を使わざるを得ません。

[non]

すると、
単純にunsigned intでキャストすると、中身（01の並び）が変わっちゃう場合があるかもしれないけど、
型を再解釈させてから代入すれば、中身は変わらないよと言うことなのでしょうか？

私の固い頭では充分な理解はできませんが、そうするものだということは憶えておきます。

[たかぎ]

すると、
単純にunsigned intでキャストすると、中身（01の並び）が変わっちゃう場合があるかもしれないけど、
型を再解釈させてから代入すれば、中身は変わらないよと言うことなのでしょうか？

そういうことです。

[non]

たかぎさん。ありがとうございました。勉強になりました。