The tag has no usage guidance.

learn more… | top users | synonyms (1)

1
vote
0answers
22 views

Is there a difference between (n - (~r % n) - 1) and (n - (abs(r) % n)) when r < 0? [migrated]

I've been studying the rotate algorithm, and came across a formula to normalize a negative number of rotations: ...
3
votes
1answer
513 views

Complexity of multiplication

I've been reading around the area of complexity and arithmetic operations using logic gates; one thing that is confusing me is that \begin{equation} \Theta (n^{2}) \end{equation} is quoted as being ...
-1
votes
0answers
21 views

Need help with binary bit pattern

Write down the binary bit pattern -1.5625 * 10^-2 assuming a format employed by the DEC PDP-8 (the leftmost 12 bits are the exponent stored as a two's complement number, and the rightmost 24 bits are ...
-1
votes
0answers
28 views

Weird question about two's complement and division

I have to answer the following multiple-choice question: We have a two's complement representation of binary numbers on 16 bits. Let be x a 16-bit string. Which sentence is true about the number ...
3
votes
1answer
57 views

What is the XNOR of 3 or more inputs?

We know that for 3 variables (A=0,B=1,C=1), f$_1$ = (A XNOR B XNOR C) = 1, since the input has even number of 1's. But if we were to do this step by step, f$_2$ = (A XNOR (B XNOR C)) = (A XNOR (1 ...
-1
votes
1answer
30 views

This opertion gives overflow and carry?

Take this example in 2's complement representation with 8 bits. 1111 1110 + 1111 1110 ( -2 + -2 = -4 ) Calculation: ...
2
votes
1answer
206 views

Full Adder vs. Half Adder

I'm having some trouble figuring out where the "Carry in" value comes from in respects to a one bit full adder diagram. I understand the below half adder, but my question is: is the the output of ...
6
votes
1answer
138 views

Sum of all products of subarrays

For any three-dimensional array $A$ of size $n_1 \times n_2 \times n_3$ let $P(A)$ be the product of all its elements, i.e. $$P(A) = \prod_{i_1 = 1}^{n_1} \prod_{i_2 = 1}^{n_2} \prod_{i_3 = 1}^{n_3} ...
0
votes
1answer
21 views

EPI question on multiplying two integers

The Elements of Programming Interviews book has a question on "computing x*y without arithmetical operators" (question 5.5). The solution is here: ...
1
vote
1answer
11 views

How to Apply Binary Transformations?

One of the steps in Binary Index Tree algorithm is to find a node's parent which is done by un-setting the rightmost SET bit. For example: if a node has index 1010 than it's parent is 1000. To apply ...
-2
votes
1answer
58 views

Turing machine for adding numbers

I'm having trouble in a certain problem. I have to write a TM that gets as an input strings $\#x\#y$ such that $x,y \in \{0,1\}^*$, and writes to the tape the output $z\#x\#y$ where $z = x+y$, all ...
1
vote
0answers
27 views

Understanding exponential computation by digit recurrence

I've met in a book the following algorithm that computes the exponential: Input: $t, n$ ($n$ is the number of steps) Output: $E_n$ $\begin{array}{l} \mbox{define $t_0 = 0$ ; $E_0 = 1$} \\ ...
2
votes
3answers
224 views

Counting an integer's divisors without just enumerating them (or estimating if not possible)?

I'm trying to count the number of divisors an integer $n$ has. The simple way to do this is to just enumerate all integers from 1 to $\sqrt{n}$, and count how many integers evenly divide $n$. For ...
1
vote
1answer
45 views

How to XOR two binary numbers having different lengths?

If we have: x = 1101 and y = 101 How to XORing these numbers?
0
votes
1answer
48 views

What this subnetting restriction means

I was reading Data Communication book by Forouzan in which there is a one restriction put on CIDR subnetting by Internet authorities: First IP address in the block should be evenly divisible by ...
1
vote
1answer
46 views

How to revert a carryless polynomial multiplication?

In the carryless multiplication of two polynomials in a 8bit environment. Is it possible to obtain the original 8bit values from the result? As an example: (x11 + x10 + x9 ) + (x7 + x5 + x4 + x3 + ...
2
votes
0answers
43 views

How to design a simpler Version of CARDIAC (Cardboard Illustrative Aid to Computers)?

I'm trying to make a simpler version of CARDIAC for only performing addition. Now, I am encountering several problems in making something similar and looking for some ideas (I'm new to Computer ...
2
votes
0answers
27 views

How can I determine if an algoritm can be expressed as a boolean circuit?

Suppose I want to express Data Encryption Standard(DES) encryption algorithm as a boolean circuit. How can I determine if what I want is practical, and if it is how can I do it?
1
vote
1answer
51 views

Adder circuit with sign bit (not twos complement)

I've found and implemented a full adder to be able to do unsigned or two's complement addition on wikipedia: https://en.wikipedia.org/wiki/Adder_(electronics)#Full_adder However, in my particular ...
2
votes
1answer
54 views

How many basic operations are there in an algorithm for the simple multiplication of two numbers of equal length?

BACKGROUND: Note: The following question arose in my mind when watching this lecture (watch at 5:30 minutes if you will). Assumption: Just for the sake of this question, let's assume that the term ...
2
votes
1answer
55 views

Alternative Method for Computing Two's Complement Binary -> Decimal

I proposed this method of converting a two's complement binary number to decimal to my professor and he said it was wrong. Some older guy in the class just shook his head at me and gave me a ...
1
vote
0answers
46 views

Dividing/Multiplying Numbers Stored in two memory locations

I have two numbers x and y. The upper bits of x are stored at location m, while the lower bits of x are stored at location n. The upper bits of y are stored at location i, while the lower bits of y ...
2
votes
1answer
65 views

In fast multiplier circuits, what is the difference between a Counter and a Compressor?

When working on fast parallel multiplier circuit designs, like Wallace tree multipliers or Dada tree multipliers I found many papers and books refer to different components used in the tree to reduce ...
5
votes
3answers
165 views

Data types for storing arbitrarily much information

I've heard that YouTube had a problem with the view count on Gangnam style since the number of views exceeded the variable byte size. What's the problem with creating really large variables? Why ...
0
votes
0answers
44 views

Could you explain this signed fixed point number equation?

How do I interpret this equation? Decimal value of signed fixed point number $-2^3+2^0+2^{-1}+2^{-2}$ $$ V = (-1)^{b_{N-1}}\times 2^{N-P-1} + \sum_{i=0}^{N-2}(b_i\times 2^i)\times 2^{-P}\,.$$ ...
-1
votes
1answer
26 views

Find variance within one pass

Given a list of real numbers. Is it possible to find the variance with no more than 1 iteration with constant space complexity? My intuition is that it is not possible. But how do I prove it ...
2
votes
2answers
97 views

Why is there more frequent overflow in normalised Floating Point

I read that overflow is more frequent when we work with normalised mantissas. Why is this? Is it because when we adopt a normalised representation, our range is smaller than in a unnormalised ...
-1
votes
1answer
179 views

Computing the number of squares which are intersected by a line internally

There's a line from (x1,y1) to (x2,y2) in a grid of squares of unit length. Write a program to compute the number of squares which are intersected by the line internally, i.e squares which are only ...
3
votes
0answers
28 views

Running time for threshold function evaluation?

A threshold function is a function $f: \{0,1\}^n \to \{0,1\}$, defined by $n$ integer-valued weights $w_1, w_2, \ldots, w_n$ and an integer valued threshold value $w_0$. It works as follows: $$f(x_1, ...
5
votes
4answers
166 views

Calculating the number of multiplications necessary to evaluate a polynomial

I was watching a lecture and got confused over a slide. This is what it says: Consider a polynomial - first representation $$P = 2 + 4x^{3} + 8x^{6} + 7x^{25} + 6x^{99}$$ The ...
9
votes
1answer
195 views

Algorithm for multiplying multivariate polynomials

Let $R$ be a commutative ring. Let $f(x_1, \dots, x_n), g(x_1, \dots, x_n)$ be two multidimensional polynomials in $R$ with maximal total degree $\delta$. How fast can we compute the product of $f$ ...
1
vote
0answers
24 views

pragmatic way to compute/ search/ match MSBs operation

consider integers represented as base 2 (strings). define a relation called "n-msb matching" that is true when the 1st n msbs (MSB is "most significant bits") match (of two integers). what is a ...
4
votes
4answers
250 views

How was the ALU implemented in the first computer (i.e., Babbage's analytical engine)?

I've seen circuit level implementations of ALU's before, but how are NOT/AND/ADD performed mechanically?
0
votes
3answers
72 views

confused about XORing and addition modulo 2

it's my understanding that when you XOR something, the result is the sum of the two numbers mod 2. why then does 4^2 = 6 and not 0? 4+2=6, 6%2 doesn't equal 6. I must be missing something about what ...
2
votes
1answer
93 views

What is this trapezoid-shaped logic component?

This is from http://www.cis.upenn.edu/~milom/cse240-Fall05/handouts/Ch05.pdf , slide 9. From this diagram, I recognize 0001 as the opcode, which corresponds to the ADD instruction. I recognize 011, ...
2
votes
1answer
59 views

Does last carry bit get added onto the sum calculated by full adder?

Note: This problem is from Introduction to Computing Systems: From Bits and Beyond(2nd) edition, 3.15, page 86. The Problem: I was able to do the problem and ended up with sum being 0010 and the ...
1
vote
1answer
220 views

Why doesn't the binary fraction representation match the decimal fraction representation?

The Problem: What value does the hexadecimal number x55544552 represent in data type IEEE floating point? My Work:     I first wrote out that hexadecimal number in binary and got ...
0
votes
1answer
78 views

How many zeros should be in front of two's complement model?

The Problem Convert 256 to its 2's complement representation. My Work    I know that 256's representation in unsigned binary is 100000000. What I know from working with two's complement ...
4
votes
2answers
174 views

Standard constructive definitions of integers, rationals, and reals?

Natural numbers are defined inductively as (using Coq syntax as an example) Inductive nat: Set := | O: nat | S: nat -> nat. Is there a standard way to define ...
1
vote
2answers
69 views

Cost of shifting a number

I was wondering what would be a time complexity of shifting a binary or a decimal number? For example: 0011, when I shift it left I get 0001. I was thinking that the time complexity is $\Theta(n)$, ...
0
votes
1answer
56 views

The logic behind one's complement addition

For my computer science class I need to finish a project where I desperately need to understand logic of one's complement and two's complement. I already know how to construct these and also how ...
0
votes
1answer
69 views

SAT for arithmetic

Given two integers $X$ and $Y$, each can be encoded in binary $X=(x_4 x_3 x_2 x_1)$ and $Y=(y_4 y_3 y_2 y_1)$, how do I encode the constraint $$|X-Y|\geq n \quad\text{and}\quad|X-Y|= n$$ when $n$ is ...
2
votes
1answer
30 views

What is considered arithmetic when dealing with bits?

In a recent homework question we were asked to implement a program that would use only bitwise operations. From our notes, this includes & | ^ ~ >> << and >>>. We are not allowed to use ...
0
votes
1answer
86 views

Binary digit problem?

Question: If a system has $32k$ bytes and each such byte has unique address(so $32k$ addresses), what is the smallest possible bits that can be use by every byte for the address ? All the bytes ...
1
vote
2answers
183 views

Fast implementation of basic addition algorithm [closed]

Write code for a modified version of the Grade School addition algorithm that adds the integer one to an m-digit integer. Thus, this modified algorithm does not even need a second number being ...
1
vote
1answer
53 views

How do you represent basic arithmetic using boolean function? [closed]

Say you have an arithmetic problem involving two variables, how do you give a Boolean formula for that using standard techniques so that one gets a minimal formula for a given number of quantifiers? ...
-1
votes
1answer
40 views

Bitwise operations on memory addresses

I have to solve a question saying The value of ab if ab & 0x3f equals 0x27. Consider a, b as hex digits. Then b&f means ...
3
votes
3answers
348 views

How can I compute an exponential modulo a large integer?

Does anyone have the computational power to check whether or not $F(m)^d \equiv m \pmod n$, where the values of the variables are found below. According to Wolfram Alpha, I found the result of the ...
1
vote
3answers
88 views

What is different between “Arithmetic Calculation” and “Calculation” in computer science?

What is different when you say "Arithmetic Calculation" and "Calculation" in the context of the computer science? The "arithmetic" in the former seems needless to me since all calculations are ...
2
votes
1answer
60 views

Why is $O(\log_{M/B} N/M)$ the same as $O(\log_{M/B} N/B)$?

Where $N$ is the size of the input, $M$ is the size of your main memory and $B$ the amount of elements that you can transfer in one I/O. My idea is that since $B$ is usually much smaller than $M$ we ...