math - 条件付き比較なしで数学的に最大値を見つける

Question

- - - - - 更新しました - - - - - -

codymanixとmoonshadowはこれまでのところ大きな助けになっています。方程式を使用して問題を解決することができました。右シフトを使用する代わりに、29で除算しました。32ビットで符号付きの場合、2 ^ 31=29にオーバーフローします。これでうまくいきます。

PHPでのプロトタイプ

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

LEADSの実際のコード（1行に1つの数学関数しか実行できません!!! AHHHH !!!）

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

----------元の質問-----------
これは私のアプリケーションの制限では完全に可能ではないと思いますが、質問する価値があると思いました。

これを簡単にしようと思います。IFや条件文を使用せずに、2つの数値の間の最大値を見つける必要があります。

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よりも大きいとは限らないことです。使用しているスクリプトアプリケーションでは、ABS、MAX、MIN、または条件付きチェックを実行できません。

上記の制限された操作を使用して、最大値に非常に近い値を見つける方法はありますか？

score 29 · Accepted Answer

2つの数値の差を見つけることができれば、これが最も簡単だと思います（大きさのみが符号ではありません）

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

ここで、はとの間の|a-b|差の大きさです。ab

score 28 · Accepted Answer

最大2つの変数を見つける：

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

ここで、>>はビット単位の右シフトです（符号に依存するSHRまたはASRとも呼ばれます）。

31の代わりに、数値のビット数から1を引いた数を使用します。

score 6 · Accepted Answer

使用可能なときに適切なブランチレス操作を生成する環境を信頼できない場合は、このページを参照して続行してください。入力範囲の制限に注意してください。入力が適合することを保証できない場合は、操作に大きな整数型を使用してください。

score 4 · Accepted Answer

条件なしのソリューション。uintにキャストしてから、intに戻ってabsを取得します。

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); }

score 3 · Accepted Answer

論理演算のみを使用し、短絡評価を行い、ゼロに向かって丸めるという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のようにフロア値に丸める規則に従っている場合は、同様のトリックを実行できます。

score 3 · Accepted Answer

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;

score 2 · Accepted Answer

うーん。NOT、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（ここでの私のロジック）

score 0 · Accepted Answer

これを試してください（ただし、オーバーフローに注意してください）（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;        
    }

score 0 · Accepted Answer

これは、一連の算術演算およびビット演算として表すことができます。例：

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;
}

score 0 · Accepted Answer

//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;

}

score 0 · Accepted Answer

+, -, *, %, /これは、演算子のみを使用した私の実装です

using static System.Console;

int Max(int a, int b) => (a + b + Abs(a - b)) / 2;
int Abs(int x) => x * ((2 * x + 1) % 2);

WriteLine(Max(-100, -2) == -2); // true
WriteLine(Max(2, -100) == 2);   // true

score 0 · Accepted Answer

私はちょうど式を思いついた： (( (a-b)-|a-b| ) / (2(a-b)) )*b + (( (b-a)-|b-a| )/(2(b-a)) )*a これはa> bの場合はaに等しく、b>aの場合はbに等しい

a> bの場合： a-b>0, a-b = |a-b|, (a-b)-|a-b| = 0 したがって、bの係数は0です。

b-a<0, b-a = -|b-a|, (b-a)-|b-a| = 2(b-a) したがって、aの係数2(b-a)/2(b-a)は1であるため、aが大きい場合は最終的に戻り0*b+1*a、その逆も同様です。

score 0 · Accepted Answer

nとmの間のMAXを見つける

MAX = ( (n/2) + (m/2) + ( ((n/2) - (m/2)) * ( (2*((n/2) - (m/2)) + 1) % 2) ) )

cで#defineを使用する：

#define MAX(n, m) ( (n/2) + (m/2) + ( ((n/2) - (m/2)) * ( (2*((n/2) - (m/2)) + 1) % 2) ) )

また

#define ABS(n) ( n * ( (2*n + 1) % 2) )  // Calculates abs value of n
#define MAX(n, m) ( (n/2) + (m/2) + ABS((n/2) - (m/2)) )  // Finds max between n & m
#define MIN(n, m) ( (n/2) + (m/2) - ABS((n/2) - (m/2)) )  // Finds min between n & m

score -1 · Accepted Answer

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

#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;
}

score -1 · Accepted Answer

Aが常にBより大きい場合..[使用できます]..MAX = (A - B) + B;

必要なし。使用するだけです：int maxA(int A, int B){ return A;}

（1）条件が許可されている場合は、次のようにしますmax = a>b ? a : b。

（2）その他の方法では、定義された数値のセットを使用するか、暗黙の条件付きチェックに依存します。

（2a）これは適切ですが、 32ビットの数値を使用max = a-((a-b)&((a-b)>>31))した場合にのみ機能します。if任意の大きな数Nを展開できますが、max（N-1、N + 1）を見つけようとすると、メソッドは失敗します。このアルゴリズムは有限状態オートマトンでは機能しますが、チューリングマシンでは機能しません。

（2b）マグニチュード|a-b|は条件です|a-b| = a-b>0 a-b : b-a

どうですか：

平方根も条件です。いつでもc>0、c^2 = d2番目の解決策が-cあり(-c)^2 = (-1)^2*c^2 = 1*c^2 = dます。平方根はペアの中で最大のものを返します。ビルドインが付属していますint max(int c1, int c2){return max(c1, c2);}

比較なしの演算子の数学は非常に対称的であり、パワーも制限されています。if正の数と負の数は、なんらかの方法なしでは区別できません。

score -1 · Accepted Answer

using System;
namespace ConsoleApp2
{
    class Program
    {
        static void Main(string[] args)
        {
            float a = 101, b = 15;
            float max = (a + b) / 2 + ((a > b) ? a - b : b - a) / 2;            
        }
    }
}

score -2 · Accepted Answer

使用している言語によって異なりますが、三項演算子が役立つ場合があります。

ただし、「スクリプトアプリケーション」で条件付きチェックを実行できない場合は、おそらく三項演算子がありません。

score -3 · Accepted Answer

#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

math - 条件付き比較なしで数学的に最大値を見つける

18 に答える 18

nとmの間のMAXを見つける

cで#defineを使用する：

また

Related

Reference