LinuxQuestions.org
Latest LQ Deal: Latest LQ Deals
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices


Reply
  Search this Thread
Old 09-16-2019, 09:45 AM   #1
Portal
LQ Newbie
 
Registered: Jun 2019
Posts: 9

Rep: Reputation: Disabled
Determine if x-y will overflow in c


I have the following homework question:

Code:
Write a function with the following prototype:
/* Determine whether arguments can be subtracted without overflow */
int tsub_ok(int x, int y);
This function should return 1 if the computation x - y does not overflow
(I am only allowed to use bit-level and logic operation, shifts, and c constants; the code should be straight line with no conditionals, loops, division, modulus, multiplication, or relative comparison operators. Assume 2's complement for signed binaries with w-bit word size)
I want to check for positive overflow and negative overflow respectively and do a bitwise-or. But I don't know how to do each respectively. Any hints?

Last edited by Portal; 09-16-2019 at 09:46 AM.
 
Old 09-16-2019, 09:46 AM   #2
pan64
LQ Guru
 
Registered: Mar 2012
Location: Hungary
Distribution: debian/ubuntu/suse ...
Posts: 13,070

Rep: Reputation: 4132Reputation: 4132Reputation: 4132Reputation: 4132Reputation: 4132Reputation: 4132Reputation: 4132Reputation: 4132Reputation: 4132Reputation: 4132Reputation: 4132
Do you know the definition of that mentioned (positive/negative) overflow? Do you know how to calculate it anyway?
Do you have already any code written?
 
1 members found this post helpful.
Old 09-16-2019, 09:51 AM   #3
Portal
LQ Newbie
 
Registered: Jun 2019
Posts: 9

Original Poster
Rep: Reputation: Disabled
I know what overflowing in the positive/negative directions looks like. I don't really have anything so far except for
Code:
int tsub_ok(int x, int y)
{
    int positive_overflow=;
    int negative_overflow=;
    return !(positive_overflow | negative_overflow);
}
 
Old 09-16-2019, 11:47 AM   #4
rtmistler
Moderator
 
Registered: Mar 2011
Location: MA, USA
Distribution: MINT Debian, Angstrom, SUSE, Ubuntu, Debian
Posts: 8,038
Blog Entries: 13

Rep: Reputation: 3488Reputation: 3488Reputation: 3488Reputation: 3488Reputation: 3488Reputation: 3488Reputation: 3488Reputation: 3488Reputation: 3488Reputation: 3488Reputation: 3488
Quote:
Originally Posted by Portal View Post
I know what overflowing in the positive/negative directions looks like. I don't really have anything so far except for
Code:
int tsub_ok(int x, int y)
{
    int positive_overflow=;
    int negative_overflow=;
    return !(positive_overflow | negative_overflow);
}
Do you understand the code defines which identify the highest and lowest integer values which the system considers to be acceptable?

Based on what you've coded, you are not demonstrating there that you know what overflowing in the positive/negative directions looks like.
 
1 members found this post helpful.
Old 09-16-2019, 01:47 PM   #5
astrogeek
Moderator
 
Registered: Oct 2008
Distribution: Slackware [64]-X.{0|1|2|37|-current} ::12<=X<=14, FreeBSD_12{.0|.1}
Posts: 5,221
Blog Entries: 11

Rep: Reputation: 3171Reputation: 3171Reputation: 3171Reputation: 3171Reputation: 3171Reputation: 3171Reputation: 3171Reputation: 3171Reputation: 3171Reputation: 3171Reputation: 3171
While we are willing to help you with homework problems, posting the problem and asking others to work it for you is not very helpful to your understanding and is not an acceptable use of the forum.

I agree that you do not appear to understand the question itself, so the best place to start is to ask your instructor to clarify the meaning of those terms, and review your course material which should have covered these by now.

As hinted by rtmistler, you will need to know the largest and smallest numbers that can be represented by the respective types, then you need to write a simple math expression which will tell you wherher adding, or subtracting some number to or from the current value will overflow or underflow that variable (without actually overflowing or underflowing).

Review your material and ask your instructor if possible, and try to work out your own solution, then ask here if you get stuck.

Good luck!
 
1 members found this post helpful.
Old 09-17-2019, 01:01 AM   #6
pan64
LQ Guru
 
Registered: Mar 2012
Location: Hungary
Distribution: debian/ubuntu/suse ...
Posts: 13,070

Rep: Reputation: 4132Reputation: 4132Reputation: 4132Reputation: 4132Reputation: 4132Reputation: 4132Reputation: 4132Reputation: 4132Reputation: 4132Reputation: 4132Reputation: 4132
what I could also imagine you explain here the steps and we will try to make it work (implement) together.
 
Old 09-17-2019, 08:11 AM   #7
NevemTeve
Senior Member
 
Registered: Oct 2011
Location: Budapest
Distribution: Debian/GNU/Linux, AIX
Posts: 3,860

Rep: Reputation: 1344Reputation: 1344Reputation: 1344Reputation: 1344Reputation: 1344Reputation: 1344Reputation: 1344Reputation: 1344Reputation: 1344Reputation: 1344
Maybe you have to reimplement binary subtration with bitwise operations.
For example the single bit 'Full Adder' is sg like this:
Code:
IN: a,b,carry_i
OUT: q,carry_o
q := a xor b xor carry_i
carry_o := a&b + (a+b)&carry_i
Maybe you have to first create a full subtractor
Code:
IN: a,b,borrow_i
OUT: q,borrow_o
q := a xor b xor borrow_i
borrow_o := ...

Last edited by NevemTeve; 09-17-2019 at 08:50 AM.
 
Old 09-18-2019, 09:30 AM   #8
rtmistler
Moderator
 
Registered: Mar 2011
Location: MA, USA
Distribution: MINT Debian, Angstrom, SUSE, Ubuntu, Debian
Posts: 8,038
Blog Entries: 13

Rep: Reputation: 3488Reputation: 3488Reputation: 3488Reputation: 3488Reputation: 3488Reputation: 3488Reputation: 3488Reputation: 3488Reputation: 3488Reputation: 3488Reputation: 3488
Quote:
Originally Posted by Portal View Post
I don't really have anything so far except for <code shown matching this description>
An additional point here is that using web search terms related to the question do yield results where the problem has been discussed with proposed solutions several times over. Top hits do not appear on this site, but do appear on at least one other technical site where code solutions are discussed.

I do hope that if anyone searches for and finds a full code solutions, that they take the time to test and verify it, as well as learn from it.

The edit says this was here on the 16th, prior to my earlier post, but I certainly missed the minute details:
Quote:
Originally Posted by Portal View Post
(I am only allowed to use bit-level and logic operation, shifts, and c constants; the code should be straight line with no conditionals, loops, division, modulus, multiplication, or relative comparison operators. Assume 2's complement for signed binaries with w-bit word size)
I do feel that one can start here with a classical, fully equipped solution which may use libraries, and some variety of techniques which do not meet the criteria here, but then tune their solution.

You can also construct the code so as to not use any #include files whatsoever, and therefore no libraries. With the exception of console or file I/O, but you can #if 0/1 those parts, use a symbolic debugger, verify with static test data, attain the solution exactly as needed, and then re-introduce the I/O libraries so that you can use a console to input and output, or files, or a combination of both.

As far as overall task flow?

I will be the first to admit that in earlier career or training, I had not always been a good student, or good at addressing tasks.

I would put forth and complete an effort, at the point where my mind had assimilated a path towards a solution.

One can joke about discovering a path towards a solution while doing dozens or entirely non-related, daily life, activities. This is extremely common, at least it is for engineers.

Meanwhile, the issue becomes far worse when the complexity and difficulty of the problem are both very high. One cannot just always just mull over a problem which involves an entire system in their mind. They certainly can, however the level of organization which they employ must be very high.

Therefore it is good advice to find a way to make progress that fits for yourself, or try to find a way to adjust your self to be capable of addressing a problem, and learn how to grow to be capable of contending with design issues of greater complexity.

And I already have described a possible direction for one possible task flow.

At this point, it really comes down to how much a person, and in this case Portal, wishes to learn from their assignments.
 
Old 09-18-2019, 12:14 PM   #9
NevemTeve
Senior Member
 
Registered: Oct 2011
Location: Budapest
Distribution: Debian/GNU/Linux, AIX
Posts: 3,860

Rep: Reputation: 1344Reputation: 1344Reputation: 1344Reputation: 1344Reputation: 1344Reputation: 1344Reputation: 1344Reputation: 1344Reputation: 1344Reputation: 1344
I'd say you should perform binary substraction then compare the borrow-bit and the sign-bit: they are equals, then there is no overflow.

Edit: Oh well, I cheated: found the solution with google. It is a bit anticlimatic though: you have to examine the sign of x, y, and x-y. (This has to be performed with a bit test, using a predefined constant from limits.h)

Last edited by NevemTeve; 09-19-2019 at 08:53 AM.
 
Old 09-19-2019, 08:08 AM   #10
bigearsbilly
Senior Member
 
Registered: Mar 2004
Location: england
Distribution: Slack, Debian, Mint, Puppy, Raspbian
Posts: 3,465

Rep: Reputation: 220Reputation: 220Reputation: 220
There are definitions for MAX and MINIMUM for most things in a header file somewhere, if you can find it
Or you could maybe use the size (in bytes) of the things in question to determine the answer?
 
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off



Similar Threads
Thread Thread Starter Forum Replies Last Post
How do i determine my IP address? How do i determine my host name? jwymore Linux - Networking 5 02-07-2007 09:57 AM
Q. What is a buffer overflow? auslew Linux - Security 2 11-08-2002 05:36 AM
OpenSSL buffer overflow attack warhorse Linux - Software 4 09-14-2002 07:26 PM
A buffer overflow attack gains an attacker an advantage when comprised by setuserid a adamrau Linux - Security 2 12-20-2001 01:32 AM
Buffer Overflow in System V Derived Login jeremy Linux - Security 0 12-13-2001 04:11 PM

LinuxQuestions.org > Forums > Non-*NIX Forums > Programming

All times are GMT -5. The time now is 10:54 PM.

Main Menu
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration