Математически найти максимальное значение без условного сравнения

Question

---------- Обновлено ------------

codymanix и moonshadow оказали большую помощь до сих пор. Я смог решить свою проблему, используя уравнения, вместо того, чтобы использовать правый сдвиг, разделенный на 29. Потому что с 32 битами, подписанными 2^31 = переполнение до 29. Это работает!

Прототип в PHP

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

Фактический код для ВЫВОДАМИ (вы можете сделать только одну математическую функцию PER ЛИНИИ !!! Аааа !!!)

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

------- --- Оригинальный вопрос -----------
Я не думаю, что это вполне возможно с ограничениями моего приложения, но я решил, что стоит попробовать.

Я постараюсь сделать это простым. Мне нужно найти максимальные значения между двумя числами, не имея возможности использовать IF или любой условный оператор.

Для того, чтобы найти значения MAX можно только выполнять следующие функции

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

Допустим, у меня есть два номера

A = 60; 
B = 50; 

Теперь, если А всегда больше, чем B, было бы легко найти максимальное значение

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

Проблема A не всегда больше B. Я cann от выполнения ABS, MAX, MIN или условных проверок с помощью скриптового приложения, которое я использую.

Можно ли использовать ограниченную операцию выше, чтобы найти значение ОЧЕНЬ близко к максимальному?

Answer 1

finding the maximum of 2 variables:

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

где >> является побитовое сдвиг вправо (также называемый SHR или ASR depeding на знаковости).

Вместо 31 вы используете количество бит, число которых имеет минус один.

Answer 2

Это зависит от того, какой язык вы используете, но может быть полезен Ternary Operator.

Но тогда, если вы не можете выполнять условные проверки в своем «скриптовом приложении», у вас, вероятно, нет тернарного оператора.

Answer 3

Хммм. Я предполагаю, что 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 

поэтому даст индекс больше бит. Ergo, сравнивайте каждый бит в обоих числах, а когда они разные, используйте указанное выше выражение (Not A и B), чтобы определить, какое число было больше. Начните с самого значащего бита и опустите оба байта. Если у вас нет петлевой конструкции, сравните каждый бит вручную.

Реализация "когда они отличаются":

(А!= B) И (моя логика здесь)

Answer 4

Если вы не можете доверять своей среде для создания соответствующих разветвленных операций, когда они доступны, см. this page о том, как действовать. Обратите внимание на ограничение на диапазон ввода; используйте большой целочисленный тип для операции, если вы не можете гарантировать, что ваши входы будут соответствовать.

Answer 5

попробовать это, (но знать для переполнения) (код в 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;   
    } 

Answer 6

Используя только логические операции, оценку короткого замыкания и предполагая 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. это можно сделать подобный трюк, если ваш язык сценариев следует соглашению округления к значению пола, как питон делает.

Answer 7

#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 

Answer 8

Я думаю, это один будет самым простейшим, если нам удастся найти разницу между двумя числами (только величина не знаком)

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

где |a-b| является величина разности между a и b ,

Answer 9

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; 

Answer 10

Решение без условных обозначений. Бросьте в 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); } 

Answer 11

Вы можете выразить это в виде ряда арифметических и битовых операций, например:

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

Answer 12

пожалуйста, посмотрите на эту программу .. это может быть лучший ответ до настоящего времени на этой странице ...

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

Answer 13

Если А всегда больше, чем в .. [мы можем использовать] .. MAX = (A - B) + B;

Не нужно. Просто используйте: int maxA(int A, int B){ return A;}

(1) Если условия разрешены, вы делаете max = a>b ? a : b.

(2) Любой другой метод использует либо определенный набор чисел, либо полагается на неявные условные проверки.

(2a) max = a-((a-b)&((a-b)>>31)) это аккуратный, но он работает только if вы используете 32-битные номера. Вы можете развернуть его произвольным большим числом N, но метод будет терпеть неудачу, если вы попытаетесь найти max (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.

Answer 14

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

}