Рубрики

Вычислить целое абсолютное значение (абс) без разветвления

Нам не нужно ничего делать, если число положительное. Мы хотим изменить только отрицательные числа. Так как отрицательные числа хранятся в форме дополнения 2 , чтобы получить абсолютное значение отрицательного числа, мы должны переключить биты числа и добавить 1 к результату.

Например, -2 в 8-битной системе сохраняется следующим образом 1 1 1 1 1 1 1 0, где крайний левый бит — знаковый бит. Чтобы получить абсолютное значение отрицательного числа, мы должны переключить все биты и добавить 1 к переключаемому числу, т. Е. 0 0 0 0 0 0 0 1 + 1 даст абсолютное значение 1 1 1 1 1 1 1 0. Также помните, что эти операции нужно выполнять только в том случае, если число отрицательное (установлен бит знака).

Способ 1
1) Установите маску как правое смещение целого числа на 31 (при условии, что целые числа хранятся с использованием 32 бит).

 mask = n>>31 

2) Для отрицательных чисел вышеприведенный шаг устанавливает маску как 1 1 1 1 1 1 1 1 и 0 0 0 0 0 0 0 0 для положительных чисел. Добавьте маску к указанному номеру.

 mask + n 

3) XOR маски + n и маска дает абсолютное значение.

 (mask + n)^mask 

Реализация:

C ++

#include <bits/stdc++.h>

using namespace std;

#define CHARBIT 8

  
/ * Эта функция вернет абсолютное значение n * /

unsigned int getAbs(int n)

{

    int const mask = n >> (sizeof(int) * CHARBIT - 1);

    return ((n + mask) ^ mask);

}

  
/ * Программа драйвера для проверки вышеуказанной функции * /

int main()

{

    int n = -6;

    cout << "Absoute value of " << n << " is " << getAbs(n);

    return 0;

}

  
// Этот код предоставлен rathbhupendra

С

#include <stdio.h>
#define CHAR_BIT 8

  
/ * Эта функция вернет абсолютное значение n * /

unsigned int getAbs(int n)

{

    int const mask = n >> (sizeof(int) * CHAR_BIT - 1);

    return ((n + mask) ^ mask);

}

  
/ * Программа драйвера для проверки вышеуказанной функции * /

int main()

{

    int n = -6;

    printf("Absoute value of %d is %u", n, getAbs(n));

  

    getchar();

    return 0;

}

Джава

// Java реализация вышеуказанного подхода

class GFG {

  

    static final int CHAR_BIT = 8;

    static final int SIZE_INT = 8;

  

    / * Эта функция вернет абсолютное значение n * /

    static int getAbs(int n)

    {

        int mask = n >> (SIZE_INT * CHAR_BIT - 1);

        return ((n + mask) ^ mask);

    }

  

    / * Код водителя * /

    public static void main(String[] args)

    {

        int n = -6;

        System.out.print("Absoute value of " + n + " is " + getAbs(n));

    }

}

  
// Этот код предоставлен Rajput-Ji

python3

# Python3 реализация вышеуказанного подхода

CHARBIT = 8;

SIZE_INT = 8;

  
# Эта функция вернет
# абсолютное значение n

def getAbs(n):

    mask = n >> (SIZE_INT * CHARBIT - 1);

    return ((n + mask) ^ mask);

  
Код водителя

n = -6;

print("Absolute value of",n,"is",getAbs(n));

  
# Этот код предоставлен mits

C #

// C # реализация вышеуказанного подхода

using System;

  

class GFG {

  

    static int CHAR_BIT = 8;

    static int SIZE_INT = 8;

  

    / * Эта функция вернет абсолютное значение n * /

    static int getAbs(int n)

    {

        int mask = n >> (SIZE_INT * CHAR_BIT - 1);

        return ((n + mask) ^ mask);

    }

  

    / * Код водителя * /

    static void Main()

    {

        int n = -6;

        Console.Write("Absoute value of " + n + " is " + getAbs(n));

    }

}

  
// Этот код предоставлен mits

PHP

<?php
// PHP реализация вышеупомянутого подхода

$CHARBIT = 8;

$SIZE_INT = 8;

  
// Эта функция вернет
// абсолютное значение n

function getAbs($n)

{

    global $SIZE_INT, $CHARBIT;

    $mask = $n >> ($SIZE_INT * $CHARBIT - 1);

    return (($n + $mask) ^ $mask);

}

  
// Код драйвера

$n = -6;

echo "Absolute value of " . $n

            " is " . getAbs($n);

  
// Этот код предоставлен mits
?>


Выход:

Absolute value of -6 is 6

Способ 2:
1) Установите маску как правое смещение целого числа на 31 (при условии, что целые числа хранятся с использованием 32 бит).

 mask = n>>31 

2) XOR маска с номером

 mask ^ n 

3) Вычтите маску из результата шага 2 и верните результат.

 (mask^n) - mask 

Реализация:

/ * Эта функция вернет абсолютное значение n * /

unsigned int getAbs(int n)

{

    int const mask = n >> (sizeof(int) * CHAR_BIT - 1);

    return ((n ^ mask) - mask);

}

На машинах, где ветвление стоит дорого, приведенное выше выражение может быть быстрее, чем очевидный подход, r = (v <0)? — (без знака) v: v, хотя количество операций одинаково.

Пожалуйста, смотрите это для более подробной информации о вышеупомянутых двух методах.

Пожалуйста, пишите комментарии, если вы обнаружите, что какое-либо из приведенных выше объяснений / алгоритмов неверно или есть лучшие способы решения той же проблемы.

Ссылки:
http://graphics.stanford.edu/~seander/bithacks.html#IntegerAbs

Рекомендуемые посты:

Вычислить целое абсолютное значение (абс) без разветвления

0.00 (0%) 0 votes