- PR -

アルゴリズム

«前のページへ 1|2|3|4|5|6|7 次のページへ»
投稿者投稿内容
がるがる
ぬし
会議室デビュー日: 2002/04/12
投稿数: 873
投稿日時: 2004-03-10 19:00
どもです。何通か電波が飛んできてる(笑)がるです。
先ほどのアルゴリズムです。

んと、言語については「特定の言語を意識せずに」かいてます。
!=が微妙かなぁとは思ったのですが、＜＞とかnot ＝ よりは
一般的に通用するかなぁ、とか思って!=にしました。

xorという演算子自体は、たしかにCにはないですね。Cだと^が
演算子になるですね。
他の言語だと…忘れてるなぁ(笑

で、ヒントを。
if内の一行目の
a = a xor b
ですが、aに入るのは「aとbのxor」です。ここはこれ以上細かく
追求せずに次の行を考えてみると…少し進むと思います ^^

ヒント２。
(x xor y) xor z == x xor y xor z == x xor (y xor z)

ヒントにならないヒント？
そういえば、昔マシン語で、メモリのクリアによく以下の
ロジックをつかってました。マシン語的にコストが安いので :-P
メモリ = メモリ xor メモリ
# 正しくはアキュムレータ相手に「アキュムレータの内容をxor」ですが :-P

-----------
この辺のアルゴリズムって「今は別にいらないジャン」とかいわれる
のですが。
例えば「桁数が極端にでかいので、16ビットの数値の四則演算よろ」と
いわれたときに
・面倒だなぁ
・え？？ どうやって作るの？？？
のいずれに自分がなりたいか、ってあたりを考えると結構重要
だと思ってます。

基礎とその応用。いずれも大切だなぁと感じる今日この頃。
unibon
ぬし
会議室デビュー日: 2002/08/22
投稿数: 1532
お住まい・勤務地: 美人谷　　　　　　　　良回答(20pt)
投稿日時: 2004-03-10 19:06
unibon です。こんにちわ。

引用:

unibonさんの書き込み (2004-03-10 18:39) より:
なお、実際にやってみて動作は分かるのですが、なぜこれでできるのかが分かりません。

少し分かりました。ということは、xor 以外、たとえば、
コード:
a = a + b;
b = a - b;
a = a - b;

でも良いですよね(言語は Java 系を想定)。
でもこれだとネタバレ感があり、トリッキーじゃなくなってしまう。
＃って、なぜトリッキーを目指す? ＞私
無月 重造
ベテラン
会議室デビュー日: 2003/12/18
投稿数: 67
投稿日時: 2004-03-10 19:11
引用:

はにまるさんの書き込み (2004-03-10 18:06) より:

　「全ビット１」と「Ｂ」の排他論理和は、「Ｂの反転ビット」ですよね．．．
　「全ビット０」と「Ｂ」の排他論理和は、「全ビット１」ですよね．．．
　「Ａ」と「Ｂ」の排他論理和は、何だ？



ちょっとまった
「全ビット０」と「Ｂ」の排他論理和は、「Ｂ」では？
がるがる
ぬし
会議室デビュー日: 2002/04/12
投稿数: 873
投稿日時: 2004-03-10 19:13
引用:

unibonさんの書き込み (2004-03-10 18:39) より:
ちなみに、私が最近、感服したアルゴリズムは、
http://www.nminoru.jp/%7Enminoru/diary/2003/09.html#2003-09-11
です。

見ました。なんていうか先人の知恵ですねぇ。ちと感動しました。
そういえば、この辺の「メモリ削減系アルゴリズム」は、ゲーム
屋さんが結構持ってることが多いような。

メンテナンス性との兼ね合いもあるのですが、リソースを可能な限り
削る手法はある程度までは我々業務系の人間にとっても重要
なように思えます。

逆に、ゲーム屋さんは我々の「メンテナンス性の高い」ものの
作り方が重要になってきているそうです。
ゆうじゅん
ぬし
会議室デビュー日: 2004/01/16
投稿数: 347
投稿日時: 2004-03-10 19:14
>はにまる様

１ビット単位で考えるとわかりやすいと思いますよ

if (a != b) {
a = a xor b　−　（１）
b = a xor b　−　（２）
a = a xor b　−　（３）
}

（１）時での組み合わせは４通り
０ Xor １　＝　■
１ Xor ０　＝　■
０ Xor ０　＝　■
１ Xor １　＝　■

それにたいして（２）を行うと
０ Xor １　＝　■ Xor １　＝　■
１ Xor ０　＝　■ Xor ０　＝　■
０ Xor ０　＝　■ Xor ０　＝　■
１ Xor １　＝　■ Xor １　＝　■

また（３）では
０ Xor １　＝　■ Xor ■　＝　■
１ Xor ０　＝　■ Xor ■　＝　■
０ Xor ０　＝　■ Xor ■　＝　■
１ Xor １　＝　■ Xor ■　＝　■


[ メッセージ編集済み 編集者: ゆうじゅん 編集日時 2004-03-10 19:16 ]
object
ぬし
会議室デビュー日: 2002/03/20
投稿数: 338
お住まい・勤務地: 香川県高松市
投稿日時: 2004-03-10 19:26
objectです。

コード:

a = a xor b
b = (a xor b) xor b
a = (a xor b) xor ((a xor b) xor b)
  = a xor b xor a xor b xor b
  = b xor a xor a xor 0
  = b xor 0
  = b

で良いのではないでしょうか？
がるがる
ぬし
会議室デビュー日: 2002/04/12
投稿数: 873
投稿日時: 2004-03-10 19:47
どもも、がるです。
引用:

unibonさんの書き込み (2004-03-10 19:06) より:
少し分かりました。ということは、xor 以外、たとえば、
コード:
a = a + b;
b = a - b;
a = a - b;

でも良いですよね(言語は Java 系を想定)。

です。
ただ、四則演算とビット演算ではビット演算のほうが「コストが安い」
処理になるので、昔は「ビット演算で出来るなら四則演算は使わない」
っていうのがありまして、こんな風になりました。

以上余談でした〜
なちゃ
ぬし
会議室デビュー日: 2003/06/11
投稿数: 872
投稿日時: 2004-03-10 20:10
引用:

一郎さんの書き込み (2004-03-10 18:41) より:

初めのif文の条件 a != b、これがヒントですね。
なんでこの条件の時だけ処理しているかという・・・

であるのですが、同時にa=bの場合は正しくない結果になるということで、最初の条件は必須だったりします。
で、よく知ってる人にはその条件だけでわかったりしますね…
«前のページへ 1|2|3|4|5|6|7 次のページへ»

スキルアップ／キャリアアップ（JOB@IT）