# bit theory, functions (one-one,onto, invertible)

• Sep 29th 2011, 06:44 PM
KavX
bit theory, functions (one-one,onto, invertible)
Hey guys

Now I understand perfectly fine what one to one, onto and invertible functions are, my troubles are when bit theory is involved with this question giving you only the length, they all seem like none are well defined.

So question is, Let Q be the set of bit strings, q, of length 64. Consider the following functions, and for those that are well defined, determine the range, and whether they are one-to-one, onto, invertible.

a) f:Q->Q, f(q) sets the left most bit of s to zero
I was told you could assume the set could be anything you want it to be, so I would just think its not onto or one to one and not well defined.

But now im not sure if thats right, and how exactly I would explain or word the answer.

b) g:Q->Q, g(q) removes the left most bit of s, I would just say its not well defined as now the length changes to 63.

c) h: Q->{0,1,2,3 .... 32}, h(q) counts the number of 1s in the leftmost 32bits of s.
This one flew over my head a bit as they seem to be giving u a set up to 32 now, and then I'm not sure what i'm comparing it against.

d) o:Q->Q, o(q) shifts the bits of s 4 places to the right discarding the 4 right most bits and setting the 4 left most bits to 0.

this seems similar to b), since its like your changing the length of the set again

e) a:Q->Q, a(q) = complement of q,
f) b:Q->Q, b(q) = q AND t where t is a fixed 64 bit string
g) y:Q->Q, y(q) = q OR t, where t is a fixed 64 bit string

Since my understanding when bit theory is involved just messes things up, doing the subsequent questions becomes impossible.

If you guys could help me do the question or point me in the right direction or atleast give me an example like this that involves bit theory with some kind of working solution.

I'd greatly appreciate any help.

Thanx
• Sep 30th 2011, 08:03 AM
CaptainBlack
Re: bit theory, functions (one-one,onto, invertible)
Quote:

Originally Posted by KavX
Hey guys

Now I understand perfectly fine what one to one, onto and invertible functions are, my troubles are when bit theory is involved with this question giving you only the length, they all seem like none are well defined.

So question is, Let Q be the set of bit strings, q, of length 64. Consider the following functions, and for those that are well defined, determine the range, and whether they are one-to-one, onto, invertible.

a) f:Q->Q, f(q) sets the left most bit of s to zero
I was told you could assume the set could be anything you want it to be, so I would just think its not onto or one to one and not well defined.

How can you assume anything about the set Q, you are told it is the set of bit strings of length 64. f maps Q to the subset of Q of 64 bit strings with a 0 in the left most bit. Every element in the range is the image of two elements in the domain.

Quote:

But now im not sure if thats right, and how exactly I would explain or word the answer.

b) g:Q->Q, g(q) removes the left most bit of s, I would just say its not well defined as now the length changes to 63.
g does not take Q into Q, so is ill defined.

Quote:

c) h: Q->{0,1,2,3 .... 32}, h(q) counts the number of 1s in the leftmost 32bits of s.
This one flew over my head a bit as they seem to be giving u a set up to 32 now, and then I'm not sure what i'm comparing it against.
The range is the set of integers 0, ... , 32, that is h maps Q to a integer between 0 and 32

Quote:

d) o:Q->Q, o(q) shifts the bits of s 4 places to the right discarding the 4 right most bits and setting the 4 left most bits to 0.

this seems similar to b), since its like your changing the length of the set again

e) a:Q->Q, a(q) = complement of q,
f) b:Q->Q, b(q) = q AND t where t is a fixed 64 bit string
g) y:Q->Q, y(q) = q OR t, where t is a fixed 64 bit string

Since my understanding when bit theory is involved just messes things up, doing the subsequent questions becomes impossible.

If you guys could help me do the question or point me in the right direction or atleast give me an example like this that involves bit theory with some kind of working solution.

I'd greatly appreciate any help.

Thanx