- bit position starts from 0 to n and not from 1 to n
- An n-bit integer in that format can store numbers between
between and so in our case, between -128 and 127.
1. how to find whether given number is power of 2
- An n-bit integer in that format can store numbers between
between and so in our case, between -128 and 127.
1. how to find whether given number is power of 2
if(n && !(n & (n-1))) { number is power of 2 }
note : number is power of 2 is different from number divisible by 2
2. if we right shift the number until it become zero then we will know the left most bit set position by subtracting the 1 from the number of shift
Ref : http://www.geeksforgeeks.org/smallest-power-of-2-greater-than-or-equal-to-n/
/* If n is a power of 2 then return n */
1 If (n & !(n&(n-1))) then return n
2 Else keep right shifting n until it becomes zero
and count no of shifts
a. Initialize: count = 0
b. While n ! = 0
n = n>>1
count = count + 1
/* Now count has the position of set bit in result */
3 Return (1 << count)
unsigned int nextPowerOf2(unsigned int n){ unsigned count = 0; /* First n in the below condition is for the case where n is 0*/ if (n && !(n&(n-1))) return n; while( n != 0) { n >>= 1; count += 1; } return 1 << count;} |
3. program to check the number of set bits in the given number n
int count_set_bits(unsigned int n){unsigned count = 0;while( n != 0){if(n & 1) {count += 1;}n >>= 1;}return count;}
Else the efficient method is below:Beauty of the this solution is number of times it loops is equal to the number of set bits in a given integer.
1 Initialize count: = 0
2 If integer n is not zero
(a) Do bitwise & with (n-1) and assign the value back to n
n: = n&(n-1)
(b) Increment count by 1
(c) go to step 2
3 Else return count
Implementation of Brian Kernighan’s Algorithm:
#include<stdio.h>
/* Function to get no of set bits in binary
representation of passed binary no. */
unsigned int countSetBits(int n)
{
unsigned int count = 0;
while (n)
{
n &= (n-1) ;
count++;
}
return count;
}
/* Program to test function countSetBits */
int main()
{
int i = 9;
printf("%d", countSetBits(i));
getchar();
return 0;
}
Example:
Example for Brian Kernighan’s Algorithm:
n = 9 (1001)
count = 0
Since 9 > 0, subtract by 1 and do bitwise & with (9-1)
n = 9&8 (1001 & 1000)
n = 8
count = 1
Since 8 > 0, subtract by 1 and do bitwise & with (8-1)
n = 8&7 (1000 & 0111)
n = 0
count = 2
Since n = 0, return count which is 2 now.
Ref : http://www.geeksforgeeks.org/count-set-bits-in-an-integer/
how negative number stored in the memory
how to check given number is negative or positive using bit programming
how to find little endian and big endian
write a program to check OS is 32 bit or 64 bit
4. this might help to find the system is 32 bit or 64 bit but not reliable. because depends on the compiler the integer size will vary . But it definitely tells that whether integer is 32 bit long or 64 bit long.
printf("\nsize of the int is %d",sizeof(int)*8);
I know it's equal to
sizeof(int). The size of an int is really compiler dependent. Back in the day, when processors were 16 bit, an int was 2 bytes. Nowadays, it's most often 4 bytes on a 32-bit as well as 64-bit systems.
Still, using
sizeof(int) is the best way to get the size of an integer for the specific system the program is executed on.
EDIT: Fixed wrong statement that
int is 8 bytes on most 64-bit systems. For example, it is 4 bytes on 64-bit GCC.
Ref: https://stackoverflow.com/questions/11438794/is-the-size-of-c-int-2-bytes-or-4-bytes
5. Program to check whether the given number is positive or negative using bitwise operator.
take example of 8 bit number.
An n-bit integer in that format can store numbers between
between and so in our case, between -128 and 127.
between and so in our case, between -128 and 127.
postive number:
- 127 = 0111 1111
- 11 = 0000 1011
negative number:
- -128 = 1000 0000
- - 11 = 1111 0101
so in the positive number MSB always 0 and in negative number LSB always 1.
// had assumption that it is 32 bit machine and integer is having size of 32 bits
int sign(int x) {
return ((x>>31)&1);
}
// better solution independent of compiler is 32 bit or 64 bit
If you can count on your compiler not being crap you should replace 31 with (CHAR_BIT*sizeof(int)-1). Portability and all that.int sign(int x) {
return ((x>>( (8*sizeof(int))-1 )&1);
}
[tselva@bng-junos-d037 /b/tselva/bcopy/bk_copy_needed/copy-needed/work_tips_dir/sample_c_program]$ cat sign.c#include<stdio.h>int main(){int a=10,b=-1;if ( a >> ((8*sizeof(int))-1)) {printf("\n a is negative");} else {printf("\n a is positive");}if ( b >> ((8*sizeof(int))-1)) {printf("\n b is negative\n");} else {printf("\n b is positive\n");}return 0;}[tselva@bng-junos-d037 /b/tselva/bcopy/bk_copy_needed/copy-needed/work_tips_dir/sample_c_program]$ ./a.outa is positiveb is negative
Ref: https://www.quora.com/How-are-negative-numbers-stored-in-memory-in-Java
https://www.reddit.com/r/C_Programming/comments/105von/how_to_check_positivezeronegative_using_bitwise/
http://graphics.stanford.edu/~seander/bithacks.html#CopyIntegerSign
6. program to check whether given two numbers having opposite sign
Detect if two integers have opposite signs
int x, y; // input values to compare signs bool f = ((x ^ y) < 0); // true iff x and y have opposite signsif(x^y) { print "both having opposite sign" }else { print "both having same sign" }
Ref:http://graphics.stanford.edu/~seander/bithacks.html#DetectOppositeSigns
7. intersting facts:
- The left shift and right shift operators should not be used for negative numbers
-The left-shift and right-shift operators are equivalent to multiplication and division by 2 respectively.
- The & operator can be used to quickly check if a number is odd or even
- The ~ operator should be used carefully
// Note that the output of following program is compiler dependentint main(){ unsigned int x = 1; printf("Signed Result %d \n", ~x); printf("Unsigned Result %ud \n", ~x); return 0;}/* Output: Signed Result -2 Unsigned Result 4294967294d */ |
8. c program to calculate the two's complement of integer number:
4 = 0100
then we invert all the bits
0100 -> 1011
finally we add one bit
1011 + 1 = 1100.
x=(~y)+1;
ref: http://www.programminglogic.com/how-computers-represent-negative-binary-numbers/
---> has to see how binary represenation of the number's two complement can be calculated
9. why two's complement of negative number stored in the memory rather than setting MSB bit as 1
-1 is represented by 11111111 (two's complement) rather than (to me more intuitive) 10000001 which is binary 1 with first bit as negative flag.
Say you have two numbers, 2 and -1. In your "intuitive" way of representing numbers, they would be
0010 and 1001, respectively (I'm sticking to 4 bits for size). In the two's complement way, they are 0010 and 1111. Now, let's say I want to add them.
Two's complement addition is very simple. You add numbers normally and any carry bit at the end is discarded. So they're added as follows:
0010
+ 1111
=10001
= 0001 (discard the carry)
0001 is 1, which is the expected result of "2+(-1)" to be.
But in your "intuitive" method, adding is more complicated:
0010
+ 1001
= 1011
Which is -3, right? Simple addition doesn't work in this case. You need to note that one of the numbers is negative and use a different algorithm if that's the case
Ref: https://stackoverflow.com/questions/1125304/why-is-twos-complement-used-to-represent-negative-numbers
10. how to find the interger max value
#define MAX_VALUE(a) (((unsigned long long)1 << (sizeof(a) * CHAR_BIT)) - 1)Definition: INT_MAX = (1 << 31) - 1 for 32-bit integer (2^31 - 1)
When using it, be careful it is assigned to a type large enough. For example:
#include <stdlib.h>
#include <stdio.h>
#include <limits.h>
#define IS_TYPE_SIGNED(a) ((a-1) < 0)
#define MAX_VALUE_UNSIGNED(a) (((unsigned long long)1 << \
(sizeof(a) * CHAR_BIT)) - 1)
#define MAX_VALUE_SIGNED(a) (MAX_VALUE_UNSIGNED(a) >> 1)
#define MAX_VALUE(a) (IS_TYPE_SIGNED(a) ? \
MAX_VALUE_SIGNED(a) : MAX_VALUE_UNSIGNED(a))
int main(void)
{
unsigned int i = 0;
signed int j = 0;
printf("%llu\n", MAX_VALUE(i));
printf("%llu\n", MAX_VALUE(j));
return EXIT_SUCCESS;
}
This prints out:
4294967295
2147483647
Ref:
https://stackoverflow.com/questions/12762040/get-the-maximum-value-of-a-variable-in-c
https://stackoverflow.com/questions/31897880/how-to-programmatically-determine-integer-max-min-in-c
11. how to swap the two values without temp variable:
#include <stdlib.h>
#include <stdio.h>
#include <limits.h>
int main(void)
{
int x=3,y=5;
x=x^y;
y=x^y;
x=x^y;
}
No comments:
Post a Comment