How to rewrite URI of custom post type?

This is what I use to rewrite custom post type URLs with the post ID. You need a rewrite rule to translate URL requests, as well as a filter on post_type_link to return the correct URLs for any calls to get_post_permalink():

add_filter('post_type_link', 'wpse33551_post_type_link', 1, 3);

function wpse33551_post_type_link( $link, $post = 0 ){
    if ( $post->post_type == 'product' ){
        return home_url( 'product/' . $post->ID );
    } else {
        return $link;
    }
}

add_action( 'init', 'wpse33551_rewrites_init' );

function wpse33551_rewrites_init(){
    add_rewrite_rule(
        'product/([0-9]+)?$',
        'index.php?post_type=product&p=$matches[1]',
        'top' );
}