交換のアルゴリズム

C algorithm

http://www.geocities.jp/ky_webid/algorithm/001.html

ある値AとBを交換しようと思ったら一時変数に代入しないと交換できない

work = a;
a = b;
b = work;

因みにPerlという言語の場合は一時変数を用意しなくても代入できる。

($a,$b) = ($b,$a);

一時変数を使わない交換

紹介されています。

b = a - b;
a -= b;
b += a;

なんか凄いですね。実際に値を設定して考えて見ましょうか。

a = 12, b = 4と仮定する

b = 12 - 4;
b = 8;
a = 12 - 8;
a = 4;
b = 8 + 4;
b = 12;

確かに値が入れ替わっています。

当然といえば当然ですね。

XORを使った交換

これはすごい。

b ^= a;
a ^= b;
b ^= a;

もうパッと見ただけでは何がなんだかわかりません。

具体的な値で確認してみましょう。

a = 00001100(12), b = 00000100(4)と仮定する

b = 00001100 ^
    00000100;

b = 00001000;

a = 00001100 ^
    00001000;

a = 00000100(4);

b = 00001000 ^
    00000100;

b = 00001100(12);

バッチリ入れ替わってますね。

交換処理の関数化

C言語は型による制限があるため、このような関数を作るのは若干不向きですね。

総称ポインタを使えば一応できるのかな？試してみた。

#include <stdio.h>

void swap(void *a, void *b) {
    *b = *a - *b;
    *a -= *b;
    *b += *a;
}

int main (void) {
    int num1 = 100;
    int num2 = 200;
    
    swap(&num1,&num2);
    
    printf("%d %d",num1,num2);
    return 0;
}

main.c(4) : error C2100: 間接指定演算子 (*) の使い方が正しくありません。
main.c(4) : error C2100: 間接指定演算子 (*) の使い方が正しくありません。
main.c(4) : error C2100: 間接指定演算子 (*) の使い方が正しくありません。
main.c(4) : error C2036: 'void *' : サイズが不明です。
main.c(4) : warning C4047: '=' : 間接参照のレベルが 'void *' と 'int' で異なっています。
main.c(5) : error C2100: 間接指定演算子 (*) の使い方が正しくありません。
main.c(5) : error C2100: 間接指定演算子 (*) の使い方が正しくありません。
main.c(5) : error C2297: '-=' : 無効です。右オペランドには型 'void *' が指定されています。
main.c(5) : error C2114: '-=' : 左オペランドがポインタなので、右オペランドは整数値でなければなりません。
main.c(6) : error C2100: 間接指定演算子 (*) の使い方が正しくありません。
main.c(6) : error C2100: 間接指定演算子 (*) の使い方が正しくありません。
main.c(6) : error C2297: '+=' : 無効です。右オペランドには型 'void *' が指定されています。
main.c(6) : error C2114: '+=' : 左オペランドがポインタなので、右オペランドは整数値でなければなりません。

というか無理ですね。

総称ポインタはポインタであればそのまま扱うことができますが、結局間接参照する際に型を指定しないといけないので意味ないですね。

void swap(void *a, void *b) {
    *(int *)b = *(int *)a - *(int *)b;
    *(int *)a -= *(int *)b;
    *(int *)b += *(int *)a;
}

総称ポインタで渡しても結局こうなる。ダメダメだ。

型が違うだけで同じような処理をしたいという場合にCでは厳しいみたいです。もちろん関数名分けたり引数で判断するというのもできなくはないですが・・。

因みにC++やJava等にはジェネリクスという機能があるらしく、それを使えば型に依存しない関数が作れるとか。凄いですね。