Q&A
C# ^演算子
で調べたりしていないのでしょうか。
配列内で一つの数字のみを求める問題で a^ = nums[i]でなんで4が求まる理由がわかりません。
ここでいう一つの数字とは[4, -1, 2, -1, 2]のうちの一つのみある4を一つの数字とする。
配列の長さを記述する時、^をVSで見た時はlength = ^に置き換えることができたので^ = lengthではないのですか？
C#
1コード 2 3int[] nums = {4, -1, 2, -1, 2 }; 4 5 public int singleNumber(int[] nums) { 6 int a = 0; 7 for (int i = 0; i < nums.Length; i++) 8 { 9 a ^= nums[i]; 10 } 11 return a; 12 }
「シングル数字」とは何でしょうか。問題の求めるところなので、ここで齟齬があれば正す必要があります。
また、「^ってlength - 1」との理解が謎です。
本質的にはXOR（EXCLUSIVE OR / 排他的論理和）を知っていることが出発点だと思いますが、いかがでしょうか。
^ = length は配列の長さです。-1は不要でした。
論理排他的 OR 演算子 = ^らしいですね。
boolについてしか書いていなかったのでint型ではどう使うかはわかりませんが。
真偽の時のみ真を返すことはわかりましたが、そこでa ^ = nuns[i] にどう関係するか意味不明です。
1T2R3M4さん、調べても理解できなかったのですがfor文の中のa ^= nums[i];を回数分処理する場合、
-4 -> -5 -> -7 -> 6 -> 4となり、4が導きだされるのですが、この計算式はいったいどういった計算なのでしょうか？
このコードは何なのです？
（ご自身で書いた？ それとも，問題の答えとして示された？）
例えば
int[] nums = {4, -1, 2, -1, 2, 2 };
とかにした時点でもう，１つしかない4を結果とできない欠陥コードに見えますが…
これは回答のコードです。もちろん、自分で正解した回答したコードもありますが、別解としてこのコードがあったので質問しました。
https://leetcode.com/problems/single-number/
問題です。
int[] nums = {4, -1, 2, -1, 2 };の配列は自分でデバックとるために適当に定義しました。
他の方も聞いてますが「シングル数字」って何？ 聞かれたことには答えませんか。話が噛み合わなくなります。
問題は質問に書き直しましたよ？
改めて言いますと、
ここでいうシングル数字とは[4, -1, 2, -1, 2]のうちの一つのみある4をシングル数字を意味します。
また、恐らくですが、配列内にはシングル数字は１つしかないと思います。
>調べても理解できなかった
どのように説明されていて、何がわからなかったのでしょうか。
^を今はboolで使われるものだと先ほど認知しました。
そこでfor文内の処理a ^= nums[i];を処理すると
計算結果が-4 -> -5 -> -7 -> 6 -> 4と導き出されなぜ4がのこるのか、^がどのように作用しているかがわかりません。
singleのほうも日本語にして、「一つの数字」としたほうがわかりやすいかと思います。
わかりました、質問を修正します。
回答2件
0
ベストアンサー
「質問への追記・修正の依頼」に何か書いてるやつらってわかってからかってるならまだしも、わかりもしないのに「質問への追記・修正の依頼」を書くやつって「自分はレベル低いですよ」って宣言してるようなもん。
この質問には回答に必要な情報は全部書いてあるのに、なんで「質問への追記・修正の依頼」が必要なんだろうね？
で、回答は排他的論理和は偶数回同じ数字が出たら消えるから２回出てきた数字は消えるんです。
でもこれだと３回出てきた数字も残るけどね。
投稿2021/04/02 04:08
退会済みユーザー
総合スコア0
なるほど！
回答がまとまっていて一番わかりやすいです。ありがとうございます。
問題文にも書かれていないのですが、恐らく、二回以下しか同じ数字は使われないのだと思います。
そのため、この計算式で通るのだと思います。
一応、手間じゃなければ、全部の数字を紙に２進数で書いて、手計算で求めてみると完璧に理解できます。
問題文中の「Constraints」に、1つのもの以外は2回出現すると書いてありますね。
ありがとうございます。
二進数について排他的論理どう使うのだろうと考えていたのですが、ようやくわかりました。
//00000100 --- 4
//11111111 --- (-1)
ここでの変換は同じ値だったら0として別の値だったら1とするという回答ですね！
//11111011 --- -5
2進数化したら-5になりました！
そうそう、その感じで５個の数字を全部計算していくと１が偶数個のbitは０になり、１が奇数個のbitは１になる。結果的に１０進数に直したとしても偶数個の数字は全部消えて、奇数個の数字だけが残る。
なるほど、めちゃくちゃ頭いい考えですね。
これはすごいです。
ありがとうございます。あんまり使う機会無いと思いますが良い経験をしました。
暗号化とかフルスクラッチで組むと使える。
bit演算の説明を16進数で書いてる人いたけどあれでわかるわけないじゃんね。
最も単純かつ解読不可能な暗号化の原理
【排他的論理和(以降 XOR と呼ぶ)】
0 XOR 0 = 0
0 XOR 1 = 1
1 XOR 0 = 1
1 XOR 1 = 0
【暗号化】
平文 キー 暗号文
0 XOR 0 = 0
0 XOR 1 = 1
1 XOR 0 = 1
1 XOR 1 = 0
【復号化】
暗号文 キー 平文
0 XOR 0 = 0
1 XOR 1 = 0
1 XOR 0 = 1
0 XOR 1 = 1
単純なXORが解読不可能とか笑わせないでください
じゃあ1bitの暗号文が0か1か特定する手段があるなら言ってみて。ないから。
1bitに意味があり、その1bitの平文を1bitの鍵長で暗号化しているという想定なんですね
一般的に使用されている暗号とは異なるようですね、すみませんでした
一般的な鍵長を想定し、単純なXORでは予測可能であるため強度が低くなります
具体的に「どのような場面」での利用を考えた暗号なのでしょうか
平文長 ≦ 鍵長
日本語が通じなかったみたいですね
ありがとうございました
その昔、その暗号方式の関数を15万円で売りました。単純なだけに低コストなマイコンなどで使える用途はあります。
最初は10万円でライブラリだけを売る契約だったんだけど、2回呼んだら平文に戻るってお客さん、えらく感動してくれて、どうしてもソースコードが欲しいとか言い出して、ソースコードは100万円とか吹っ掛ければ良かったなと後になって思ったけど5万円欲しかったんでライブラリ10万円、ソースコード5万円、合わせて15万円で売ったわ。
バーナム暗号のようなものをイメージしています
低コストなマイコンには向かないと思うのですが、その時、鍵はどのようにしていたのでしょうか
解読不可能という話の続きだと思っていますが、使い回したりしてないですよね
まあ、15万円程度じゃ暗号としては難読化程度でもいいということかもしれませんが
低コストなマイコンで実現可能な、解読不可能な暗号が実装できればそれこそ世界が変わりますね
鍵をどう扱ってたのかは知らない。
インターネット越しに暗号化ライブラリを作って欲しいと注文が来ただけだから。
引数がデータと鍵とデータ長の関数を作っただけ。
＞暗号としては難読化程度でも
それは違う。
鍵の扱い方次第で解読不可能になる。
> 鍵の扱い方次第で解読不可能になる。
解読不可能な使い方が低コストなマイコンでは現実的でない、ということです
だから、「鍵はどのようにしていたのでしょうか」と聞きました、知らないんですよね
あー、はい。
勘違いでした。
0
ブール論理演算子 - C# リファレンス | Microsoft Docs
より引用
「^ 演算子は、そのオペランドの論理排他的 OR (論理 XOR とも呼ばれます) を計算します。 x が true に評価され、y が false に評価された場合、または x が false に評価され、y が true に評価された場合、x ^ y の結果は true です。 それ以外の場合、結果は false です。 つまり、bool オペランドの場合、^ 演算子は非等値演算子 != と同じ結果を計算します。」
C#
1Console.WriteLine(true ^ true); // output: False 2Console.WriteLine(true ^ false); // output: True 3Console.WriteLine(false ^ true); // output: True 4Console.WriteLine(false ^ false); // output: False
複合代入
「2 項演算子 op の場合、フォームの複合代入式」
C#
1x op= y
上記の式は、次の式と同じです。
C#
1x = x op y
投稿2021/04/02 04:10
総合スコア1638
x += 1;のようによく書く式ですね。
^だけ別の作用すると思っていました。
例えば、
x = 4;
y = -1;
でx ^ yが真となりますが、この回答が-5になるのはなぜですか?
4 ^ -1 = -(4+1)ってことですか？
ただ符号が別の時全く違う回答になります。
＞@showkitさん
本質問の場合は演算の対象がbool型ではなくint型であるので、ブールの論理演算ではなくビットごとの論理演算です。
https://docs.microsoft.com/ja-jp/dotnet/csharp/language-reference/operators/bitwise-and-shift-operators#logical-exclusive-or-operator-
わかったからBA選んだんじゃないの？
本件で ^ で行っているのは，true or false な世界の論理演算じゃなくてbit演算だということと，
整数が実際にどのようなbitパターンで表現されるのかということ（負の値であれば補数表現）
を知る必要がある．
（上っ面の説明に飛びついてBAに選ぶ前に，せめて実際にbitパターンで確認してみればいいのに）
dodox86さん。
これがteratail_dayoさんの言う二進数での計算ってことですか？
訂正-->bitパターンの計算で求まる
fanaさん、今回の質問に対しての求める回答については4がなぜ求まるかの理由ですよ？
そしてそれ理解できたのでBA選んだのです。
これはshowkitさんの回答の話になります。
BAを選んだ方ははっきり理解しやすいように説明してくださったからです。
式だけでは4が求まるかは意味が分かりません。
32bit で考えるとして
4 は 0x00000004
-1 は 0xFFFFFFFF これを排他的論理和でとると
0xFFFFFFFB で、10進数で表現すると -5 になります。
2021/04/02 13:50 のコメントは
「4 ^ -1 が何で-5になるのか？」とか言ってるのを受けてとのこと．
なるほど。bit計算も考える必要があるということですね。
この回答なら理解できます。
fanaさん、回答してくださりありがとうございます。
> [4, -1, 2, -1, 2]
の最初の２つのXORがわからん状態なら，全要素のXORが4になることは大抵わからんのではないのか，という素朴な疑問を抱いたのです．
あなたの回答
tips
プレビュー
