Labels

.NET Job Questions About Java Absract class Abstract class Abstract Class and Interface Aggregation ajax aop apache ofbiz Apache ofbiz tutrial Association authentication autocad basics batch Binary Tree bootstrap loader in java build Builder design pattern C++ Job Questions caching CallableStatement in java certifications Chain of responsibility Design pattern charts check parentheses in a string Classes classloader in java classloading concept code quality collage level java program Composition concurrency Concurrency Tutorial Converting InputStream to String Core Java core java concept core java interview questions Core Java Interview Questions Core Java Questions core java tutorial CyclicBarrier in Java data structures database Database Job Questions datetime in c# DB Db2 SQL Replication deserialization in java Design Patterns designpatterns Downloads dtd Eclipse ejb example/sample code exception handling in core java file handling injava File I/O vs Memory-Mapped Filter first program in spring flex Garbage Collection Generics concept in java grails groovy and grails Guice Heap hibernate Hibernate Interview Questions how-to IBM DB2 IBM DB2 Tutorial ide immutable Interceptor Interface interview Interview Questions for Advanced JAVA investment bank j2ee java JAVA Code Examples Java 7 java changes java class loading JAVA Classes and Objects Java Classloader concept Java classloading concept java cloning concept java collection Java collection interview questions Java Collections java concurrency Java CountDownLatch java definiton Java design pattern Java EE 5 Java EE 6 Java Exceptions Java file Java Garbage Collection Java generics Java Glossary java hot concept java immutable concept Java Interface Java interview Question java interview question 2012 java interview question answer Java Interview Questions Java Interview Questions and Answers java interview topic java investment bank Java Job Questions java multithreading java multithreading concept java new features Java Packages java proxy object java questions Java Serialization Java serialization concept java serialization interview question java session concept java string Java Swings Questions java synchronization java threading Java Threads Questions java tutorial java util; java collections; java questions java volatile java volatile interview question Java Wrapper Classes java.java1.5 java.lang.ClassCastException JavaNotes javascript JAX-WS jdbc JDBC JDBC Database connection jdk 1.5 features JDK 1.5 new features Concurrent HashMap JMS interview question JMS tutorial job JSESSIONID concept JSESSIONID interview Question JSF jsp JSP Interview Question JSP taglib JSTL with JSP Junit Junit Concept Junit interview question.Best Practices to write JUnit test cases in Java JVM Linux - Unix tutorial Marker Interfaces MD5 encryption and decryption messaging MNC software java interview question musix NCR java interview question Networking Job Questions news Object Serialization Objects ojdbc14.jar OOP Oracle Oracle SQL Query for two timestamp difference orm own JavaScript function call in Apache ofbiz Packages Palm Apps patterns pdf persistence Portal Portlet Spring Integration Prime number test in java programs Rails Reboot remote computers REST Ruby Sample application schema SCJP security Senior java developer interviews servlet3 servlets session tracking singleton design pattern Spring Spring 2.5 Framework spring ebook Spring framework concept spring MVC spring pdf Spring Security Spring Security interview questions SQL SQL performance SQL Query to create xml file Sql Query tuning ssis and ssrs StAX and XML string concept string immutable string in java strings struts Struts2 Struts2 integration synchronization works in java Technical Interview testing tips Tomcat top Tutorial Volatile in deep Volatile working concept web Web Developer Job Questions web services weblogic Weblogic Application Server websphere what is JSESSIONID xml XML parsing in java XML with Java xslt


Wednesday, 17 July 2013

Bits and Bytes - C Interview Questions


Q. What is the most efficient way to store flag values?
A flag is a value used to make a decision between two or more options in the execution of a program. For instance, the /w flag on the MS-DOS dir command causes the command to display filenames in several columns across the screen instead of displaying them one per line. In which a flag is used to indicate which of two possible types is held in a union. Because a flag has a small number of values (often only two), it is tempting to save memory space by not storing each flag in its own int or char.
Efficiency in this case is a tradeoff between size and speed. The most memory-space efficient way to store a flag value is as single bits or groups of bits just large enough to hold all the possible values. This is because most computers cannot address individual bits in memory, so the bit or bits of interest must be extracted from the bytes that contain it.
The most time-efficient way to store flag values is to keep each in its own integer variable. Unfortunately, this method can waste up to 31 bits of a 32-bit variable, which can lead to very inefficient use of memory. If there are only a few flags, it doesn't matter how they are stored. If there are many flags, it might be advantageous to store them packed in an array of characters or integers. They must then be extracted by a process called bit masking, in which unwanted bits are removed from the ones of interest.
Sometimes it is possible to combine a flag with another value to save space. It might be possible to use high- order bits of integers that have values smaller than what an integer can hold. Another possibility is that some data is always a multiple of 2 or 4, so the low-order bits can be used to store a flag.
Q. What is meant by "bit masking"?
Bit masking means selecting only certain bits from byte(s) that might have many bits set. To examine some bits of a byte, the byte is bitwise "ANDed" with a mask that is a number consisting of only those bits of interest. For instance, to look at the one's digit (rightmost digit) of the variable flags, you bitwise AND it with a mask of one (the bitwise AND operator in C is &):
flags & 1;
To set the bits of interest, the number is bitwise "ORed" with the bit mask (the bitwise OR operator in C is |). For instance, you could set the one's digit of flags like so:
flags = flags | 1;
Or, equivalently, you could set it like this:
flags |= 1;
To clear the bits of interest, the number is bitwise ANDed with the one's complement of the bit mask. The "one's complement" of a number is the number with all its one bits changed to zeros and all its zero bits changed to ones. The one's complement operator in C is ~. For instance, you could clear the one's digit of flags like so:
flags = flags & ~1;
Or, equivalently, you could clear it like this:
flags &= ~1;
Sometimes it is easier to use macros to manipulate flag values.
Example Program : Macros that make manipulating flags easier.
/* Bit Masking */
/* Bit masking can be used to switch a character
   between lowercase and uppercase */
#define BIT_POS(N)            ( 1U << (N) )
#define SET_FLAG(N, F)        ( (N) |= (F) )
#define CLR_FLAG(N, F)        ( (N) &= -(F) )
#define TST_FLAG(N, F)        ( (N) & (F) )
#define BIT_RANGE(N, M)       ( BIT_POS((M)+1 - (N))-1 << (N) )
#define BIT_SHIFTL(B, N)      ( (unsigned)(B) << (N) )
#define BIT_SHIFTR(B, N)      ( (unsigned)(B) >> (N) )
#define SET_MFLAG(N, F, V)    ( CLR_FLAG(N, F), SET_FLAG(N, V) )
#define CLR_MFLAG(N, F)       ( (N) &= ~(F) )
#define GET_MFLAG(N, F)       ( (N) & (F) )
#include <stdio.h>
void main()
{
  unsigned char ascii_char = 'A';        /*  char = 8 bits only */
  int test_nbr = 10;
  printf("Starting character = %c\n", ascii_char);
  /*  The 5th bit position determines if the character is
      uppercase or lowercase.
      5th bit = 0  - Uppercase
      5th bit = 1  - Lowercase      */
  printf("\nTurn 5th bit on = %c\n", SET_FLAG(ascii_char, BIT_POS(5)) );
  printf("Turn 5th bit off = %c\n\n", CLR_FLAG(ascii_char, BIT_POS(5)) );
  printf("Look at shifting bits\n");
  printf("=====================\n");
  printf("Current value = %d\n", test_nbr);
  printf("Shifting one position left = %d\n",
         test_nbr = BIT_SHIFTL(test_nbr, 1) );
  printf("Shifting two positions right = %d\n",
         BIT_SHIFTR(test_nbr, 2) );
}
BIT_POS(N) takes an integer N and returns a bit mask corresponding to that single bit position (BIT_POS(0)returns a bit mask for the one's digit, BIT_POS(1) returns a bit mask for the two's digit, and so on). So instead of writing
#define A_FLAG 4096
#define B_FLAG 8192
you can write
#define A_FLAG BIT_POS(12)
#define B_FLAG BIT_POS(13)
which is less prone to errors.
The SET_FLAG(N, F) macro sets the bit at position F of variable N. Its opposite is CLR_FLAG(N, F), which clears the bit at position F of variable N. Finally, TST_FLAG(N, F) can be used to test the value of the bit at position F of variable N, as in
if (TST_FLAG(flags, A_FLAG))
        /* do something */;
The macro BIT_RANGE(N, M) produces a bit mask corresponding to bit positions N through M, inclusive. With this macro, instead of writing
#define FIRST_OCTAL_DIGIT 7 /* 111 */
#define SECOND_OCTAL_DIGIT 56 /* 111000 */
you can write
#define FIRST_OCTAL_DIGIT BIT_RANGE(0, 2) /* 111 */
#define SECOND_OCTAL_DIGIT BIT_RANGE(3, 5) /* 111000 */
which more clearly indicates which bits are meant.
The macro BIT_SHIFT(B, N) can be used to shift value B into the proper bit range (starting with bit N). For instance, if you had a flag called C that could take on one of five possible colors, the colors might be defined like this:
#define C_FLAG          BIT_RANGE(8, 10)      /* 11100000000 */
/* here are all the values the C flag can take on */
#define C_BLACK         BIT_SHIFTL(0, 8)       /* 00000000000 */
#define C_RED           BIT_SHIFTL(1, 8)       /* 00100000000 */
#define C_GREEN         BIT_SHIFTL(2, 8)       /* 01000000000 */
#define C_BLUE          BIT_SHIFTL(3, 8)       /* 01100000000 */
#define C_WHITE         BIT_SHIFTL(4, 8)       /* 10000000000 */
#define C_ZERO          C_BLACK
#define C_LARGEST       C_WHITE
/* A truly paranoid programmer might do this */
#if C_LARGEST > C_FLAG
        Cause an error message. The flag C_FLAG is not
        big enough to hold all its possible values.
#endif /* C_LARGEST > C_FLAG */
The macro SET_MFLAG(N, F, V) sets flag F in variable N to the value V. The macro CLR_MFLAG(N, F) is identical toCLR_FLAG(N, F), except the name is changed so that all the operations on multibit flags have a similar naming convention. The macro GET_MFLAG(N, F) gets the value of flag F in variable N, so it can be tested, as in
if (GET_MFLAG(flags, C_FLAG) == C_BLUE)
        /* do something */;
Q. Are bit fields portable?
Bit fields are not portable. Because bit fields cannot span machine words, and because the number of bits in a machine word is different on different machines, a particular program using bit fields might not even compile on a particular machine.
Assuming that your program does compile, the order in which bits are assigned to bit fields is not defined. Therefore, different compilers, or even different versions of the same compiler, could produce code that would not work properly on data generated by compiled older code. Stay away from using bit fields, except in cases in which the machine can directly address bits in memory and the compiler can generate code to take advantage of it and the increase in speed to be gained would be essential to the operation of the program.
Q. Is it better to bitshift a value than to multiply by 2?
Any decent optimizing compiler will generate the same code no matter which way you write it. Use whichever form is more readable in the context in which it appears. The following program's assembler code can be viewed with a tool such as CODEVIEW on DOS/Windows or the disassembler (usually called "dis") on UNIX machines:
Example: Multiplying by 2 and shifting left by 1 are often the same.
void main()
{
  unsigned int test_nbr = 300;
  test_nbr *= 2;
  test_nbr = 300;
  test_nbr <<= 1;
}

No comments:

Post a Comment

LinkWithin

Related Posts Plugin for WordPress, Blogger...