Videos
The shortest solution in your first piece of code is to change the printf statement as follows:
printf("absValue = %u\n", (unsigned)((u<0)?-u:u));
This will print the absolute value of u. The type conversion (unsigned) ensures that the data type is as expected by printf. The statement (u<0)?-u:u uses the conditional operator to select the value -u if the condition (u<0) is true and u if the condition is false (i.e. u>=0).
The problem in your code is that u is a signed integer which means its value is stored using the Two's complement representation in 4 bytes(*) and printf is not intelligent. When you tell printf to display an unsigned integer, then printf will take the 4 bytes holding u and interpret them as an unsigned integer. Since negative numbers in Two's complement are stored as large positive integers, that is the result you see.
(*) The use of Two's complement and the int size of 4 is machine-dependent, but common.
As an alternative, you can also use the standard C function abs() (or one of its related functions):
7.22.6.1 The abs, labs and llabs functions
Synopsis
#include <stdlib.h> int abs(int j); long int labs(long int j); long long int llabs(long long int j);Description
The
abs,labs, andllabsfunctions compute the absolute value of an integerj. If the result cannot be represented, the behavior is undefined.Returns
The
abs,labs, andllabs, functions return the absolute value.Footnotes
The absolute value of the most negative number cannot be represented in two's complement.
Note the footnote "The absolute value of the most negative number cannot be represented in two's complement." and "If the result cannot be represented, the behavior is undefined." Strictly speaking, you'd likely need to use long long int and llabs() to avoid undefined behavior in converting INT_MIN to a positive value, assuming a 32-bit int value, and long is often 32-bits, even on 64-bit Windows.
However, since double values are likely implemented in IEEE format with 53 bits of precision, a 32-bit int value can be converted to double with no loss of precision, so you can use the fabs() function to get the absolute value of a 32-bit int value in one call:
7.12.7.2 The fabs functions
Synopsis
#include <math.h> double fabs(double x); float fabsf(float x); long double fabsl(long double x);The
fabsfunctions compute the absolute value of a floating-point numberx.
So your code would be:
#include <stdio.h>
#include <math.h>
int main (int argc, char *argv[]) {
int u;
scanf("%d", &u);
printf("absValue = %u\n", (unsigned) fabs((double) u));
return 0;
}
Note that in (unsigned) fabs((double) u), casting u to double is not strictly necessary, as the int value will be implicitly converted to a double because of the double fabs(double) function prototype from stdlib.h. But the cast back to unsigned is exremely necessary to pass the unsigned int value you want to pass to printf().
You could also do this:
#include <stdio.h>
#include <math.h>
int main (int argc, char *argv[]) {
int u;
scanf("%d", &u);
unsigned int absValue = fabs(u);
printf("absValue = %u\n", absValue);
return 0;
}
That works because unsigned int absValue is explicitly an unsigned int.
Also, on modern CPUs, conversion between int and double is usually done by a single relatively fast instruction.
In the course of the algorithm, some array entries are set to negative values as a marker. Therefore the entries' absolute value has to be taken when they are used as indices into the array.
In the hope of not spoiling anything:
The algorithm requires that the array entries of an n-element array all are between 1 and n inclusive.
If any entry is larger than n or smaller than -n or 0, it will access invalid addresses, and if any element is negative, the marking logic will fail.
The logic of the algorithm is:
for each array element e:
if the value at (e-1) is positive, e has not yet been seen,
negate the value at (e-1) to mark e as seen
otherwise, e has already been seen, so print it
So since array entries become negative in the course of running the algorithm, the absolute value has to be taken to obtain valid indices.
Let us follow the algorithm for a modified example to see how it works:
before: arr = { 7, 3, 4, 5, 5, 3, 2}
i == 0: arr[0] = 7
arr[7-1] is 2 > 0 ~> negate
arr = { 7, 3, 4, 5, 5, 3, -2}
i == 1: arr[1] = 3
arr[3-1] is 4 > 0 ~> negate
arr = { 7, 3, -4, 5, 5, 3, -2}
i == 2: arr[2] is -4 ~> abs for indexing
arr[4-1] is 5 > 0 ~> negate
arr = { 7, 3, -4,-5, 5, 3, -2}
i == 3: arr[3] is -5 ~> abs for indexing
arr[5-1] is 5 > 0 ~> negate
arr = { 7, 3, -4, -5, -5, 3, -2}
i == 4: arr[4] is -5 ~> abs for indexing
arr[5-1] is -5 < 0 ~> print abs(-5) as duplicate
i == 5: arr[5] is 3
arr[3-1] is -4 < 0 ~> print abs(3) as duplicate
i == 6: arr[6] is -2 ~> abs for indexing
arr[2-1] is 3 > 0 ~> negate
arr = { 7, -3, -4, -5, -5, 3, -2}
indices of positive entries: 0, 5 ~> 1 and 6 not in original array
indices of negative entries: 1, 2, 3, 4, 6 ~> 2, 3, 4, 5, 7 in original array
If you had started with the most straightforward way to solve this, given additional O(n) space, you would have probably thought about storing "already encountered" flags in a separate (auxiliary) array to look them up afterwards:
// pseudocode (zero based indexing ignored for now)
for each value in array
if (already_encountered[value] == true)
print "found a duplicate of " + value
else
already_encountered[value] = true
Your algorithm goes a little further. Given the fact that an integer is (probably) 32-bit, and you only need to store a limited (small) range of values, each array member actually has sufficient free bits to store the "already encountered" flag.
This means that you can drop the auxiliary already_encountered array given above, and use this extra space to store the flags with no extra memory allocation.
Using some bit twiddling, you could, for example, choose to store this value at the highest bit (leaving you with 31 bits to store your numbers). Whenever you want to check if the flag is set, you would need to extract this highest bit and check it, and then finally clear the bit before printing out the value:
// pseudocode (zero based indexing ignored)
for each value in array
{
// this value might already have a flag previously encoded
// for some other element, so remove it before continuing
plain_value = remove_flag(value)
// check if the flag is set for the actual value,
// if not, set it now
if (is_flag_set(array[plain_value]) == true)
print "found a duplicate of " + plain_value
else
array[plain_value] = set_flag(array[plain_value])
}
The only thing left to do is to define set_flag, is_flag_set and remove_flag functions.
In your case, the algorithm "sets the flag" by negating the value, "tests for flag" by checking if the value is negative, and "removes the flag" by using the absolute value (hence the abs function).
This can be safely achieved because signed integers use a single bit to store their sign information, allowing the transformation to leave the original value intact (provided it is small enough).
This leaves you with your final C code:
void printTwoElements(int arr[], int size)
{
int i;
printf("\n The repeating element is");
for(i = 0; i < size; i++)
{
// remove the flag
int plain_value = abs(arr[i]);
// is flag set?
if(arr[plain_value-1] < 0)
{
printf(" %d ", plain_value);
}
else
{
// set the flag by negating
arr[plain_value-1] = -arr[plain_value-1];
}
}
}
The standard C library is providing the optimized solutions for many problems with considerations based on the architecture, compiler in use and others. The abs() function defined in stdlib.h is one of these, and it is used for your purpose exactly. To emphasize the point, here is ARM compiler result when using abs vs a version of a homebrew abs: https://arm.godbolt.org/z/aO7t1n
Paste:
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
srand(111);
int x = rand() - 200;
printf("%d\n", abs(x));
}
results in
main:
push {r4, lr}
mov r0, #111
bl srand
bl rand
sub r1, r0, #200
cmp r1, #0
rsblt r1, r1, #0
ldr r0, .L4
bl printf
mov r0, #0
pop {r4, pc}
.L4:
.word .LC0
.LC0:
.ascii "%d\012\000"
And
#include <stdio.h>
#include <stdlib.h>
int my_abs(int x)
{
return x < 0 ? -x : x;
}
int main(void)
{
srand(111);
int x = rand() - 200;
printf("%d\n", my_abs(x));
}
results in
my_abs:
cmp r0, #0
rsblt r0, r0, #0
bx lr
main:
push {r4, lr}
mov r0, #111
bl srand
bl rand
sub r1, r0, #200
cmp r1, #0
rsblt r1, r1, #0
ldr r0, .L5
bl printf
mov r0, #0
pop {r4, pc}
.L5:
.word .LC0
.LC0:
.ascii "%d\012\000"
Notice that the main code is identical (only a label name is different) in both programs as my_abs got inlined, and its implementation is the same as the standard one.
The speed of a given solution will depend greatly on the architecture, but in C I would say
return (n > 0 ? n : -n);
and let the compiler figure out the best solution.
EDIT: @jonk points out correctly that this will fail for the most-negative possible value of n, assuming that two's-complement arithmetic is used.
Yes, my solution has a conditional branch, but yours has an arithmetic operator and two bitwise operators. Can your microcontroller shift 15 places in a single clock?
So, I was thinking of making fast abs function, which would be necesary to improve performance, and I had an idea to do it something like this
int abs(int input){
return input & -0;
}Essentially, I am trying to make a simple function that removes the sign bit. The problem is, I heard that alot of compliers would ignore this because its a zero. How could I do it that compliers wouldnt ignore it, and it would work for the intended purpose?
Edit: Thanks for all the answers the issue has been resolved!