数学的には、条件の比較せずに最大値を探します

https://stackoverflow.com/questions/1375882

21-09-2019
|

質問

----------更新------------

codymanixと、これまで大きな助けとなっているmoonshadow。私は式を使用して私の問題を解決することができたし、代わりに右シフトを使用するため、私は32ビットと29で割っ=作品29にオーバーフローする！2 ^ 31を締結しました。

PHPでのプロトタイプ

$r = $x - (($x - $y) & (($x - $y) / (29)));

LEADSの実際のコード（あなたが唯一の数学関数PER LINEを行うことができます!!! AHHHH !!!）

DERIVDE1 = IMAGE1 - IMAGE2;
DERIVED2 = DERIVED1 / 29;
DERIVED3 = DERIVED1 AND DERIVED2;
MAX = IMAGE1 - DERIVED3;

----------元の質問-----------
私は、これは自分のアプリケーションの制限が十分に可能であるとは思わないが、私はそれの価値が依頼するショットを考え出します。

私はこの単純なを作るしようとするでしょう。私は、IFまたは任意の条件文を使用できずに二つの数値間の最大値を見つける必要があります。

MAX値私は、次の機能を実行することができますを見つけるために、

Divide, Multiply, Subtract, Add, NOT, AND ,OR

私は2つの数値を持ってみましょうと言う。

A = 60;
B = 50;

Aは常にBよりも大きければ今では最大値

を見つけることができるシンプルなだろう

MAX = (A - B) + B;
ex. 
10 = (60 - 50)
10 + 50 = 60 = MAX

問題は、Aは常にB.私が使用していたスクリプトapplicaitonとABS、MAX、MINまたは条件チェックを実行することはできませんよりも大きくないとされます。

非常に近いmaxに値を見つけるために、上記の限定された操作を使用して可能どのような方法がありますか？

解決

2つの変数の最大値を求める：の

max = a-((a-b)&((a-b)>>31))

（また、SHRまたはASR符号の有無にdepedingと呼ばれる）を右シフトビット単位である>>

の代わりに31のあなたの番号は持っているビットの数マイナス1を使用します。

他のヒント

私は（唯一の大きさは署名しない）私たちは二つの数値の違いを見つけるために管理する場合はこの1つは、ほとんどの最も簡単だろうと思います。

max = ((a+b)+|a-b|)/2;

|a-b|はaとbの差の大きさである

あなたは、彼らが利用可能な適切な無店舗オペレーションを生成するために、ご使用の環境を信頼できない場合は、

は、参照<のhref =「http://graphics.stanford.edu/~seander/bithacks.html#IntegerMinOrMax」のrel =」 noreferrer ">続行する方法については、このページ。入力範囲の制限に注意してください。あなたの入力が収まる保証できない場合は、操作のためのより大きな整数型を使用します。

条件文のないソリューション。キャスト腹筋を取得するために戻ってint型へ、その後uintにます。

int abs (a) { return (int)((unsigned int)a); }
int max (a, b) { return (a + b + abs(a - b)) / 2; }

int max3 (a, b, c) { return (max(max(a,b),c); }

、唯一短絡評価を論理演算を使用して、ゼロに向かって丸めのC規則を仮定すると、これを表現することが可能です

int lt0(int x) {
    return x && (!!((x-1)/x));
}

int mymax(int a, int b) {
    return lt0(a-b)*b+lt0(b-a)*a;
}

基本的な考え方は、0または1を返します。比較演算子を実装することで、あなたのスクリプト言語はPythonのようなフロア値に向かって丸めの規則はありません。

以下の場合には、同様のトリックを行うことが可能です

うーん。私は仮定しないで、AND、OR、およびビット単位ですか？もしそうなら、これを解決するためのビット単位の表現があるように起こっています。なお、A | Bは、数> = Aを与えると> = B.がおそらく最もビットの数を選択するための剪定方法があります。

拡張するために、我々は、A（0）又はB（1）が大きいかどうかを判断するために、次の必要があります。

真理値表：

0|0 = 0  
0|1 = 1
1|0 = 0
1|1 = 0

!A and B

は、したがって、より大きなビットの指標を与えます。エルゴは、両方の番号の各ビットを比較し、それらが異なる場合、大きいあった数を決定するために、上記式（ませんAおよびB）を使用します。最上位ビットからスタートし、両方のバイトを下に進みます。あなたは何のループ構造を持っていない場合は、手動で各ビットを比較します。

"彼らは異なっている" 実装ます：

（A！= B）AND（ここでは私のロジック）

function Min(x,y:integer):integer;
  Var
   d:integer;
   abs:integer;
 begin
  d:=x-y;
  abs:=d*(1-2*((3*d) div (3*d+1)));
  Result:=(x+y-abs) div 2;
 end;

、これを試してみてください（ただし、オーバーフローのために注意してください）（C＃でコード）

    public static Int32 Maximum(params Int32[] values)
    {
        Int32 retVal = Int32.MinValue;
        foreach (Int32 i in values)
            retVal += (((i - retVal) >> 31) & (i - retVal));
        return retVal;        
    }

あなた例えば、算術及びビット単位の一連の動作としてこれを表現することができる：

int myabs(const int& in) {
  const int tmp = in >> ((sizeof(int) * CHAR_BIT) - 1);
  return tmp - (in ^ tmp(;
}

int mymax(int a, int b) {
    return ((a+b) + myabs(b-a)) / 2;
}

してくださいこのプログラムを見て。これは、このページの日付までの最良の答えかもしれません...

#include <stdio.h>

int main()
{
    int a,b;
    a=3;
    b=5;
    printf("%d %d\n",a,b);
    b = (a+b)-(a=b); // this line is doing the reversal
    printf("%d %d\n",a,b);
    return 0;
}

//Assuming 32 bit integers 
int is_diff_positive(int num)
{
    ((num & 0x80000000) >> 31) ^ 1; // if diff positive ret 1 else 0
}
int sign(int x)
{
   return ((num & 0x80000000) >> 31);
}

int flip(int x)
{
   return x ^ 1;
}

int max(int a, int b)
{
  int diff = a - b;

  int is_pos_a = sign(a);
  int is_pos_b = sign(b);

  int is_diff_positive = diff_positive(diff);
  int is_diff_neg = flip(is_diff_positive);

  // diff (a - b) will overflow / underflow if signs are opposite
  // ex: a = INT_MAX , b = -3 then a - b => INT_MAX - (-3) => INT_MAX + 3
  int can_overflow = is_pos_a ^ is_pos_b;
  int cannot_overflow = flip(can_overflow);
  int res = (cannot_overflow * ( (a * is_diff_positive) + (b * 
            is_diff_negative)) + (can_overflow * ( (a * is_pos_a) + (b * 
            is_pos_b)));

  return res;

}

それはあなたが使用しているどの言語によって異なりますが、三項演算子には便利かもしれません。

しかし、その後、あなたはあなたの "スクリプトのアプリケーションの中で、条件チェックを実行できない場合、あなたはおそらく、三項演算子を持っていません。

Aは常にBよりも大きい場合.. .. MAX = (A - B) + B;
[我々は使用することができます]

必要はありません。ただ、使用：int maxA(int A, int B){ return A;}

条件文は、あなたがmax = a>b ? a : bを行う許可されている場合は、

（1）。

（2）他の方法のいずれかが数値の定義されたセットを使用するか、暗黙の条件チェックに依存している。

この

（2A）max = a-((a-b)&((a-b)>>31))はきちんとしているが、それはあなたが32ビットの数値を使用しifに動作します。あなたはそれが多数のNを任意拡大することができますが、最大（N-1、N + 1）を見つけるためにしようとした場合の方法は失敗します。このアルゴリズムは、有限状態オートマトンではなく、チューリングマシンで動作します。

（2B）マグニチュード|a-b|が条件である|a-b| = a-b>0 a-b : b-a

何について：
の

平方根も条件です。たびc>0とc^2 = dたちは-cので、第二の溶液の(-c)^2 = (-1)^2*c^2 = 1*c^2 = dを持っています。平方根はペアで最大を返します。私はint max(int c1, int c2){return max(c1, c2);}でビルドが付属しています。

比較演算子の数学なし

は非常に対称ならびに電力が制限されます。正と負の数はいくつかの並べ替えのifなしに区別することはできません。

#region GetMaximumNumber
/// <summary>
/// Provides method to get maximum values.
/// </summary>
/// <param name="values">Integer array for getting maximum values.</param>
/// <returns>Maximum number from an array.</returns>
private int GetMaximumNumber(params int[] values)
{
  // Declare to store the maximum number.
  int maximumNumber = 0;
  try
  {
    // Check that array is not null and array has an elements.
    if (values != null &&
        values.Length > 0)
    {
      // Sort the array in ascending order for getting maximum value.
      Array.Sort(values);

      // Get the last value from an array which is always maximum.
      maximumNumber = values[values.Length - 1];
    }
  }
  catch (Exception ex)
  {
    throw ex;
  }
  return maximumNumber;
}
#endregion

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow